什么是树形DP？

概念：

给定一棵有N个节点的树(通常是无根树，也就是有N-1条无向边)，我们可以任选一个节点为根节点，从而定义出每个节点的深度和每棵子树的根。

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

如何树形DP？

树形DP一般可以解决三类问题： ①最大独立子集 ②树的重心 ③树的直径 而这三类问题是树形dp题的基础。

最大独立子集

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

最经典的莫过于这道题：

没有上司的晚会

题目描述 Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起参加宴会。

输入格式 第一行一个整数N。(1≤N≤6000) 接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128≤Ri≤127) 接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。 最后一行输入0,0。

输出格式 第1行：输出最大的快乐指数。

样例 样例输入 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 样例输出 5

分析

建立一个二维DP，第一维是节点的编号(也是子树的根)，第二维是这个根节点参加与否，比如dp[3][1]表示以3号节点为子树的根，当它参会时整棵子树的快乐指数和；dp[3][0]表示以3号节点为子树的根，当它不参会时整棵子树的快乐指数和；这样就可以满足最优子结构的性质了。 $$dp[i][0]=max(dp[k][0],dp[k][1])$$

$$dp[i][1]=dp[k][0]+w[i]$$

注意：本题输入的是一棵有根树(制定了节点间的上下关系)，故我们需要先找出没有上司的节点root作为根，DP的目标答案在 $max(dp[root][1],dp[root][0])$中。 时间复杂度为O(n)。

#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #define max(x,y) x>y?x:y using namespace std; const int M=1e5+5; int a[M]; vector<int> G[M]; bool flag[M]; int dp[M][5]; void read(int &x) { x = 0; int f = 1; char s = getchar(); while (s > '9' || s < '0') { if (s == '-') f = -1; s = getchar(); } while (s >= '0' && s <= '9') { x = (x << 3) + (x << 1) + (s - '0'); s = getchar(); } x *= f; }//读优 void dfs(int x){ dp[x][0]=0,dp[x][1]=a[x]; for(int i=0;i<G[x].size();i++){ int id=G[x][i]; dfs(id); dp[x][0]+=max(dp[id][0],dp[id][1]); dp[x][1]+=dp[id][0]; } } int main(){ int n; read(n); for(int i=1;i<=n;i++){ read(a[i]); } for(int i=1;i<n;i++){ int l,k; read(l),read(k); G[k].push_back(l); flag[l]=true; } for(int i=1;i<=n;i++){ if(flag[i]==false){ dfs(i); printf("%d",max(dp[i][1],dp[i][0])); return 0; } } return 0; } /* 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0 5 */

---

树的重心

树的重心定义为，当把节点x去掉后，其最大子树的节点个数最少(或者说成最大连通块的节点数最少)，那么节点x就是树的重心。

在求树的重心中，有以下几个定理要用到：

1、删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心，且相邻； 2、树中所有节点到重心的距离之和最小，如果有两个重心，那么它们距离之和相等； 3、两个树通过一条边合并，新的重心在原树两个重心的路径上； 4、树删除或添加一个叶子节点，重心最多只移动一条边。 反正现在看了也不懂

先来看一道题：

求树的重心

题目描述 树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。如下图,当去掉点1后，树将分成两个连通块：（2,4,5），（3,6,7），则最大的连通块包含节点个数为3。若去掉点2，则树将分成3个部分，（4），（5），（1,3,6,7）最大的连通块包含4个节点；第一种方法可以得到更小的最大联通分量。可以发现，其他方案不可能得到比3更小的值了。所以，点1是树的重心。

输入格式 输入：第一行一个整数n，表示树的结点个数。（n<100） 接下来n-1行，每行两个数i，j。表示i和j有边相连。

输出格式 输出：第一行一个整数k，表示重心的个数。 接下来K行，每行一个整数，表示重心。按从小到大的顺序给出。

样例 样例输入 7 1 2 1 3 2 4 2 5 3 6 3 7 样例输出 1 1

分析

因为无根，所以要自己设一个根，这也是树形dp常用的方法。

                $dp[i]=$${\sum }_{j\in Son(i)}$ $dp[j]+1$

那么假设i是重心，在删除$i$之后$max(dp[j])(j\in Son(i))$还要与i上面的所有节点(可看成一棵子树)比，也就是$n-dp[i]$。右图中我们假设2号节点是重心，那么除了他们儿子节点为根的子树4和5以外，还有1367节点也可看成一棵子树，所以$f[i]=max(max(dp[j]),n-dp[i])$(f[i]就是以i为重心的最大子树节点数)，那么答案就是$min(f[i])(i\in (1n))$

搜索时，还是递归到底层，回溯时进行累加，再利用重心的性质，所有 子树的节点数不超过总节点数的1/2，更新flag的值，就可以找到重心节点了。

代码

#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #define max(x,y) x>y?x:y #define min(x,y) x>y?y:x using namespace std; const int M=1e5+5; vector<int> G[M]; bool flag[M]; int dp[M],siz[M]; int ans=0x3f3f3f3f,cnt; int n; void dfs(int x,int y){ int maxn=0; dp[x]=1; for(int i=0;i<G[x].size();i++){ int id=G[x][i]; if(id!=y){ dfs(id,x); dp[x]+=dp[id]; maxn=max(maxn,dp[id]); } } maxn=max(maxn,n-dp[x]); if(maxn<ans){ ans=maxn; cnt=0; siz[++cnt]=x; } else if(maxn==ans){ siz[++cnt]=x; } } void add_edge(int x,int y){ G[x].push_back(y); G[y].push_back(x); } int main(){ scanf("%d",&n); for(int i=1;i<=n-1;i++){ int l,k; scanf("%d %d",&l,&k); add_edge(l,k); } dfs(1,0); printf("%d\n",cnt); sort(siz+1,siz+1+cnt); for(int i=1;i<=cnt;i++){ printf("%d\n",siz[i]); } return 0; }

---

树的直径

给定一棵树,树中每条边都有一个权值,树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点(两个节点肯定都是叶子节点)之间的距离被称为树的直径,连接这两点的路径被称为树的最长链。后者通常也可称为直径。

有以下两棵相同树，但是根不同：(推荐一个作图网站这里) 而两棵树的直径却是相同的，所以我们还是可以自定根节点 不妨设1号节点为根，“N个节点，N-1条边的无向图”就可以看作“有根树”。设d[x]表示从节点x出发走向以x为根的子树，能够到达最远节点的距离。设x的子节点为y1，y2，……，yt，edge(x, y)表示边权，显然有：            $d[x]=max${$d[yi]+edge(x,yi)$} $(1\le i\le t)$ 接下来，我们可以考虑对每个节点x求出“经过节点x的最长链的长度”ans[x],整棵树的直径就是：                  $max${$ans[x]$}$(1\le x\le n)$

那么，如何求ans[x]呢？我们用链式前向星存图，依次遍历以x为起点的所有连边，用已经更新过的d[x]与没有枚举到的x的连边之和来更新ans[x]: $$ans[x]=max(ans[x],d[x]+d[yi]+edge(x,yi))$$ 然后再不断更新 $$d[x]=max(d[x],d[yi]+edge(x,yi))$$

#include<cstdio> #include<algorithm> #include<cstring> #include<vector> #define max(x,y) x>y?x:y #define min(x,y) x>y?y:x using namespace std; const int M=1e5+5; struct node{ int val,t; node(){} node(int T,int V){ t=T,val=V; } }; vector<node> G[M]; int ans,dp[M]; bool flag[M]; void dfs(int x){ flag[x]=true; for(int i=0;i<G[x].size();i++){ int yi=G[x][i].t; if(flag[yi]) continue; dfs(yi); ans=max(ans,dp[x]+dp[yi]+G[x][i].val); dp[x]=max(dp[x],dp[yi]+G[x][i].val); } } void add_edge(int x,int y,int z){ G[x].push_back(node(y,z)); G[y].push_back(node(x,z)); } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n-1;i++){ int u,v,w=1; scanf("%d %d",&u,&v); add_edge(u,v,w); } dfs(1); printf("%d",ans); return 0; }

代码纯手打，点个赞再走呗！