​ 以此题作为树形DP的入门。

树形 DP，即在树上进行的 DP。由于树固有的递归性质，树形 DP 一般都是递归进行的。——OI Wiki

分析

​ 我们从这一题给出的样例开始分析。

​ 由题意可知，对于每一个点，只有选或不选两种状态，且相邻的点不能同时选取。

​ 考虑以 $i$ 作为根节点的子树中选取或不选取 $i$ 的两种情况。

​

​ 由此就可以很容易得到递推公式

$$\begin{aligned} f(i,0)&=f(i,0)+\max \{ f(r,0),f(r,1) \} \\ f(i,1)&=f(i,1)+f(r,0) \end{aligned}$$

​ 那么 $\max { f(r,0),f(r,1) }$ 即为最终答案(r为根节点)。

代码

#include <bits/stdc++.h>
using namespace std;
// f[i][0]表示以i为根的子树中不选i时的最大值
// f[i][1]表示以i为根的子树中选i时的最大值
// f[i][1]=r[u] f[i][1]+=f[v][0] 选i不选i的儿子
// f[i][0]+=max(f[i][1],f[i][0]) 不选i可选可不选i的儿子
//显然的 设整个子树的根为r max(f[r][0],f[r][1])就是最终的答案
const int N = 6005, M = N * 2;
int r[N], f[N][2], n, first[N], nxt[M], v[M], idx;
void add(int x, int y) {
    v[++idx] = y;
    nxt[idx] = first[x];
    first[x] = idx;
}
void dfs(int u, int father) {
    f[u][1] = r[u];
    for (int i = first[u]; i; i = nxt[i]) {
        int p = v[i];
        if (p != father) {  //不判重则会导致死循环
            dfs(p, u);      //回溯push_up
            f[u][0] += max(f[p][0], f[p][1]);
            f[u][1] += f[p][0];
        }
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &r[i]);
    }
    for (int i = 1; i <= n - 1; i++) {
        int l, k;
        scanf("%d%d", &l, &k);
        add(l, k);
        add(k, l);
    }
    dfs(1, -1);
    int ans = max(f[1][0], f[1][1]);
    printf("%d", ans);
    return 0;
}