树形dp入门

POJ2342

一棵树，每个节点有权值，儿子与父亲不能同时取，求解从树上选取点能获得的最大权值

dp[i][0]表示不取，dp[i][1]表示取。

设j为i的儿子节点，dp[i][0] += max(dp[j][0], dp[j][1]), dp[i][1] += dp[j][0];

入度为零的点是根，从根开始进行深搜。

 1 #include <vector>
 2 #include <cstring>
 3 #include <cstdio>
 4 using namespace std;
 5 typedef long long LL;
 6 
 7 const int maxn = 6e3 + 10;
 8 int N;
 9 int dp[maxn][2];
10 bool in[maxn];
11 vector<int> tr[maxn];
12 
13 void dfs(int u) {
14     for (int i = 0; i < tr[u].size(); i++) {
15         int v = tr[u][i];
16         dfs(v);
17         dp[u][1] += dp[v][0];
18         dp[u][0] += max(dp[v][1], dp[v][0]);
19     }
20 }
21 
22 int main() {
23     while (~scanf("%d", &N)) {
24         memset(in, 0, sizeof(in));
25         memset(dp, 0, sizeof(dp));
26         for (int i = 0; i <= N; i++) tr[i].clear();
27         for (int i = 1; i <= N; i++) scanf("%d", &dp[i][1]);
28         int root = 1;
29         int u, v;
30         while (scanf("%d%d", &u, &v), u + v) {
31             tr[v].push_back(u);
32             in[u] = 1;
33         }
34         for (int i = 1; i <= N; i++) if (in[i] == 0) 
35             root = i;
36         dfs(root);
37         printf("%d
", max(dp[root][0], dp[root][1]));
38     }
39     return 0;
40 }