主体思路
说实话,这题的树形dp思路比本题的数据处理还要来的简单直接
状态表示
dp[u][0]: 在所有以u为根的子树中选择,且不选u的方案
dp[u][1]: 在所有以u为根的子树中选择,且选u的方案
状态计算
dp[u][0]: 累加u的每个子树s的max(dp[s][0], dp[s][1])
dp[u][1]: 先加自己的happy[u]
, 再累加u的每个子树s的dp[s][0]
注意细节
【树的存储】
参考这里 常用代码模板2——数据结构
【~i】
老师给的代码中,写着 ~i
在go语言中,要写成 i != -1
基础代码
package main
import "fmt"
const N int = 6010
var (
n, idx int
h, e, ne, happy [N]int
has_fa [N]bool
dp [N][2]int
)
func add(a, b int) { e[idx] = b; ne[idx] = h[a]; h[a] = idx; idx++ }
func max(a, b int) int { if a > b { return a }; return b }
func dfs(u int) {
dp[u][1] = happy[u]
for i := h[u]; i != -1; i = ne[i] {
j := e[i]
dfs(j)
dp[u][1] += dp[j][0]
dp[u][0] += max(dp[j][0], dp[j][1])
}
}
func main() {
fmt.Scanf("%d", &n)
for i := 1; i <= n; i++ { fmt.Scanf("%d", &happy[i]) }
for i := range h { h[i] = -1 }
for i := 0; i < n - 1; i++ {
var a, b int
fmt.Scanf("%d%d", &a, &b)
add(b, a)
has_fa[a] = true
}
root := 1
for has_fa[root] { root++ } // 找出谁是root
dfs(root)
fmt.Println(max(dp[root][0], dp[root][1]))
}