题目描述

Ural 大学有 $N$ 名职员，编号为$1∼N$。

他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。

每个职员有一个快乐指数，用整数$H_i$ 给出，其中 $1≤i≤N$。

现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。

在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

问题分析

题意就是在一棵树中选择点，使得所选点的权重和最大，有一个限制：子节点和它的父节点不在同一个方案中。

算法设计

树形DP。

代码实现

package main
import "fmt"

func main(){
    var n int
    fmt.Scan(&n)


    st := make([]bool, n + 1)
    happy := make([]int, n + 1)
    for i := 1;i <= n;i ++{
        fmt.Scan(&happy[i])
    }
    // 存储父子节点之间的连接
    dict := make(map[int][]int)
    var c,p int
    for i:=0;i < n-1;i ++{
        fmt.Scan(&c,&p)
        st[c] = true
        if _,ok := dict[p]; ok{
            dict[p] = append(dict[p],c)
        }else{
            dict[p] = []int{c}
        }
    }
    // 寻找根节点
    root := 1
    for st[root] {
        root ++
    }

    // 创建状态表示f
    f:= make([][]int, n + 1)
    for i := 0;i <=n;i ++{
        f[i] = make([]int, 2)
    }

    var dfs func(u int)


    dfs = func(u int){
        f[u][1] = happy[u]
        for _,idx := range dict[u]{
            dfs(idx)
            f[u][0] += max(f[idx][0], f[idx][1])
            f[u][1] += f[idx][0]
        }
    }

    dfs(root)

    fmt.Println(max(f[root][0],f[root][1]))

}



func max(x,y int) int{
    if x > y{

        return x
    }

    return y

}

复杂度分析

对于每一个父节点会遍历它的每一个子节点，故时间复杂度为$O(n)$