[TOC] # 树形DP 树形 DP，即在树上进行的 DP。考虑树的边和点的取舍问题。.由于树固有的递归性质，树形 DP 一般都是递归进行的。 这样讲可能有点抽象，我们以一道经典树形DP问题为例。 ## 没有上司的舞会 [题目连接](https://www.luogu.org/problemnew/show/P1352) ### 题意描述 有一个公司，这个公司的职员关系结构是一颗树，也就是说，一个人最多有一个上司，但可以有多个手下。并且每个人有一个快乐值 ​ 。现在，公司要举行一个舞会，但是，没有人想和自己的上司一起参加舞会，现在问你参加舞会的人的快乐值之和最大可以是多少。 ### 分析 因为题目保证了职员关系结构是一棵树，而且因为关系是有向的，所以一定有一个点没有上司，这个点也就是树的根。从根出发考虑这个问题，对于当前节点来说，如果我们选择当前节点那么我们就不能选择这个节点的直接后继节点，而如果不选的话，就没有限制了。 ### 状态与转移方程 用dp[x](#)表示不选择x这个点，用dp[x](#)表示选择这个点。用set(x)表示x节点的后继节点，也就是x的下手。 那么可得转移方程： > dp\[x\]\[1\] = \\sum\_{i\\in set(x)} dp\[i\]\[0\] > dp\[x\]\[0\] = \\sum\_{i\\in set(x)}max(dp\[i\]\[0\], dp\[i\]\[1\])​ ### 复杂度和代码 时间复杂度：O(n)， 空间复杂度：O(n)。 ~~~ #include <bits/stdc++.h> using namespace std; const int MAXN = 6e3 + 7; ​ int a[MAXN], fa[MAXN]; vector<int> G[MAXN]; //dp[x][0]表示不包含x，dp[x][1]表示包含x。 int dfs(int x, int t){ int ans = 0; if(t == 0){ for(auto p: G[x]){ ans += max(dfs(p, 0), dfs(p, 1)); } } else{ for(auto p: G[x]){ ans += dfs(p, 0); } ans += a[x]; } return ans; } int main(int argc, char const *argv[]) { int n; while(cin >> n){ for(int i=1;i<=n;++i){ cin >> a[i]; fa[i] = 0; G[i].clear(); } int u, v; while(cin >> u >> v){ if(u || v){ G[v].push_back(u); fa[u]++; } else break; } int root; for(int i=1;i<=n;++i) if(fa[i] == 0) root = i; //求根节点 cout << max(dfs(root, 1), dfs(root, 0)) << endl; } return 0; } ~~~ ## 习题 [HDU 2196 Computer](http://acm.hdu.edu.cn/showproblem.php?pid=2196) [POJ 1463 Strategic game](http://poj.org/problem?id=1463) [POJ 3585 Accumulation Degree](http://poj.org/problem?id=3585)