树形DP

概念

给定一棵有N个节点的树(通常是无根树，也就是有N-1条无向边)，我们可以任选一个节点为根节点，从而定义出每个节点的深度和每棵子树的根。 在树上设计动态规划算法时，一般就以节点从深到浅(子树从小到大)的顺序作为DP的“阶段”。DP的状态表示中，第一维通常是节点编号(代表以该节点为根的子树)。大多数时候，我们采用递归的方式实现树形动态规划。对于每个节点x，先递归在它的每个子节点上进行DP，在回溯时，从子节点向节点x进行状态转移。

用途

最大独立子集

最大独立子集的定义是，对于一个树形结构，所有的孩子和他们的父亲存在排斥，也就是如果选取了某个节点，那么会导致不能选取这个节点的所有孩子节点。一般询问是要求给出当前这颗树的最大独立子集的大小(被选择的节点个数)。

例题 没有上司的晚会.

~~简单的操作不说了~~ 递归+回溯，分成选与不选，分别存储，最后比个MAX #include<cstdio> #include<vector> using namespace std; vector<int> v[6005]; int h[6005], flag[6005], dp[6005][5], root; int Max(int x, int y) { return x > y ? x : y; } void Dp(int root) { dp[root][0] = 0; dp[root][1] = h[root]; for(int i = 0; i < v[root].size(); i ++) { int son = v[root][i]; Dp(son); dp[root][0] += Max(dp[son][1], dp[son][0]); dp[root][1] += dp[son][0]; } } int main() { int n, x, y; scanf("%d", &n); for(int i = 1; i <= n; i ++) scanf("%d", &h[i]); for(int i = 1; i <= n - 1; i ++) { scanf("%d %d", &x, &y); v[y].push_back(x); flag[x] = 1; } for(int i = 1; i <= n; i ++) { if(!flag[i]) { root = i; break; } } Dp(root); printf("%d", Max(dp[root][1], dp[root][0])); }

树的重心

树的重心定义为，当把节点x去掉后，其最大子树的节点个数最少(或者说成最大连通块的节点数最少)，那么节点x就是树的重心。 需要注意的是重心最多只有两个，并且节点数一定小于等于总和 (原因易证)利用这些定理就可以解决啦 #include<cstdio> #include<vector> #include<iostream> using namespace std; int dp[105], tot, n, ans1, ans2; bool flag[105]; vector<int> v[105]; int Max(int x, int y) { return x > y ? x : y; } int Min(int x, int y) { return x < y ? x : y; } void DP(int root) { bool f = 0; dp[root] = 1; for(int i = 0; i < v[root].size(); i ++) { int son = v[root][i]; if(!flag[son]) { flag[son] = 1; DP(son); dp[root] += dp[son]; if(dp[son] > n / 2) { f = 1; } } } if(n - dp[root] > n / 2) { f = 1; } if(!f) { tot ++; if(!ans1) ans1 = root; else ans2 = root; } } int main() { int x, y, ans = -0x7f7f7f7f; scanf("%d", &n); for(int i = 1; i <= n - 1; i ++) { scanf("%d %d", &x, &y); v[x].push_back(y); v[y].push_back(x); } flag[1] = 1; DP(1); printf("%d\n", tot); if(tot == 1) printf("%d", ans1); else printf("%d\n%d", Min(ans1, ans2), Max(ans1, ans2)); }

树的直径

给定一棵树,树中每条边都有一个权值,树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点(两个节点肯定都是叶子节点)之间的距离被称为树的直径,连接这两点的路径被称为树的最长链。后者通常也可称为直径。 好像有很多种做法这里就说一下树形DP做法 求出最长的一条链，每次判断更新，别忘了更新ans（用最长的链加上当前的链以及权值），最后输出ans就可以啦 #include<cstdio> #include<vector> using namespace std; bool flag[200005]; int dp[200005], head[200005], to[200005], next[200005], tot, ans; int Max(int x, int y) { return x > y ? x : y; } int Min(int x, int y) { return x < y ? x : y; } void add(int x, int y) { to[++tot] = y; next[tot] = head[x]; head[x] = tot; } void DP(int x) { for(int i = head[x]; i; i = next[i]) { int t = to[i]; if(flag[t]) continue; flag[t] = 1; DP(t); ans = Max(ans, dp[x] + dp[t] + 1); dp[x] = Max(dp[x], dp[t] + 1); } } int main() { int n, x, y, ansz = -1; scanf("%d", &n); for(int i = 1; i <= n - 1; i ++) { scanf("%d %d", &x, &y); add(x, y); add(y, x); } flag[1] = 1; DP(1); printf("%d", ans); }