概念

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

作用

最大独立子集

对于一个树形结构，所有的孩子和他们的父亲存在排斥(选了孩子就不能选父亲，泛指同理)，一般询问能选的最多的权值之和(被选择的节点个数)。 eg:没有上司的晚会

这道题是典型的最大独立子集，"没有职员愿和直接上司一起参加宴会"也就相当于子节点与父节点产生排斥关系，于是也就变成了最大独立子集的一道板题。 我们可以设一个数组dp[i][j]，其中i表示节点编号，j只包括0,1，表示选不选这一个结点，于是就可以推出两个dp式子： $$dp[i][0]=max(dp[k][0],dp[k][1])$$$$dp[i][1]=dp[k][0]+wt[i]$$ 其中k为i的一个子节点,wt[i]表示第i个节点的权重 推出式子后，就可以树形dp，依次往下搜索，推到叶节点后返回来回溯执行这个式子。 核心代码:

void tree_dp(int x) { dp[x][0] = 0; dp[x][1] = h[x]; for(int i = head[x];i;i = edge[i].next) { int to = edge[i].to; tree_dp(to); dp[x][0] += max(dp[to][0],dp[to][1]); dp[x][1] += dp[to][0]; } }

树的重心

将一个结点去掉后，最大子树结点最少，则称这个结点为一棵树的重心。 其中重心有这样一些性质:

1、删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心，且相邻；

2、树中所有节点到重心的距离之和最小，如果有两个重心，那么它们距离之和相等；

3、两个树通过一条边合并，新的重心在原树两个重心的路径上；

4、树删除或添加一个叶子节点，重心最多只移动一条边。

我们可以分别设两个数组dp和f，表示当前结点下子树节点的总个数和将当前结点去掉后最大子树结点的个数，也可以推出这样两个式子： $$dp[i]=dp[i]+dp[k]$$$$f[i]=max(max(dp[k]),n-dp[i])$$

其中结点·k是结点i的子结点，n是结点的总个数。 核心代码:

void tree_dfs(int x) { dp[x] = 1; int maxx = 0; for(int i = 0;i < vec[x].size();i ++) { int to = vec[x][i]; if(!vis[to]) { vis[to] = 1; tree_dfs(to); dp[x] += dp[to]; maxx = max(maxx,dp[to]); } } f[x] = max(maxx,n - dp[x]); }

树的直径

给定一棵树,树中每条边都有一个权值,树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点(两个节点肯定都是叶子节点)之间的距离被称为树的直径,连接这两点的路径被称为树的最长链。后者通常也可称为直径。 求树的直径可以用搜索或树形dp来做，用两个数组dp1,dp2分别表示以这个点为根结点的并且过这个点的最长链和次长链，最长链与次长链长度的总和就是以这个点为根结点的树的直径。可以由这个结点的子结点的最长链和次长链来获取这个结点的最长链与次长链，可以推出以下几个式子: $$dp1[x]=min(dp1[to]+1,dp1[x])$$$$dp2[x]=min(dp1[to]+1,dp2[x])$$$$ans=Max(ans,dp2[x]+dp1[x])$$ 其中第一个式子未更新的话才会执行第二个式子。 核心代码：

void tree_dp(int x) { for(int i = head[x];i;i = edge[i].next) { int to = edge[i].to; if(!vis[to]) { vis[to] = 1; tree_dp(to); if(dp1[x] < dp1[to] + 1) { dp2[x] = dp1[x]; dp1[x] = dp1[to] + 1; } else if(dp2[x] < dp1[to] + 1) dp2[x] = dp1[to] + 1; ans = Max(ans,dp2[x] + dp1[x]); } } }

End