树型动态规划，顾名思义，在“树”上进行状态转移，状态转移关系往往建立在父节点和子节点之间，“树”上父子关系天然就是一个递归（重叠子问题），建立起父亲、儿子之间关系，然后记忆化搜索实现。 建立递推关系（状态转移方程），可以从这样两个方向进行：

（1）子节点→父节点，父节点的值建立在子节点基础上进行；

（2）父节点→子节点，已经得到整个树的信息，也就是父节点的值，求某一个字节的值，往往用于换根 Dp。

例1.P1352没有上司的舞会

【思路点拨】

对于一个节点，这个节点可以参加或不参加 $(0/1)$ 舞会。如果某个节点参加了，那么这个节点的子节点（下属）都不能来参加，如果这个节点没有参加，那么这个节点的子节点可以参加或者不能参加，那么定义 $f[x][1]$ 表示以 $x$ 节点为根的子树，节点 $x$ 参加的情况下，这颗子树的所能获得的最大快乐指数，$f[x][0]$ 节点 $i$ 不参加所能获得的最大快乐指数。

$r[x]$ 是节点 $i$ 的快乐指数。状态转移方程为：

$f[x][0]=\sum max(f[son_x][1],f[son_x][0])$

$f[x][1]=r[x]+\sum f[son_x][0]$

$ans=max(f[root][0],f[root][1])$

参考代码：

版本1：动态数组存树

版本2：链式前向星

例2.P2016 战略游戏

【思路点拨】

根据题意构建一张关系图，关系图是一颗树，点上安排士兵，用士兵看边，使用最少的士兵看住所有的边。（最少的点看住所有的边）

1.设 $f[x][1]$ 表示以 $x$ 为根的子树中，$x$ 安排士兵，以 $x$ 为根的子树需要最少士兵。此时 $x$ 的子节点可以安排士兵，也可以不安排。

$f[x][1]=1+\sum min(f[y][0],f[y][1])$,$y$ 是 $x$ 的子节点

2.设 $f[x][0]$ 表示以 $x$ 为根的子树中，$x$ 不安排士兵，以 $x$ 为根的子树需要最少士兵。此时 $x$ 的子节点 $y$ 必须安排士兵，否则边 $(x,y)$ 将无人瞭望。

$f[x][0]=\sum f[y][1]$,$y$ 是 $x$ 的子节点

$ans=min(f[root][0],f[root][1])$

参考代码：

版本1：动态数组

版本2：链式前向星

例3.P2458 [SDOI2006]保安站岗

题意简化，给定一棵，给树上一些点安排士兵看守树上所有的点，任意一个点都能看守其父亲、儿子，每个点安排士兵的费用不同，问要看守住所有树上的节点，最少花费是多少？（点看守点）

对于树上每一个点，这个点要被看守住，可能是被父亲看住、自己看自己、儿子看住$3$种情况，那针对这三种情况，设计状态转移如下：

1.$f[x][0]$：$x$ 被父亲看到，这时 $x$ 没有安排警卫，$x$ 的儿子要么安排警卫，要么被它的后代看到，则：

$f[x][0]=\sum min(f[y][1],f[y][2])$

2.$f[x][1]$：$x$ 被儿子看到，即 $x$ 的某个儿子安排了警卫，其他儿子需要安排警卫或者被它的后代看到，则：

$f[x][1]=(\sum min(f[y][1],f[y][2]) ) +d$

其中 $d= min(d,f[y][2]-min(f[y][1],f[y][2]))$

关于$d$的理解：$x$被儿子看到，那么$x$的所有儿子中至少有一个应该安排警卫，就会有两张情况：

（1）如果所有儿子 $f[y][1]<f[y][2]$,那么就需要找一个最小安排花费的儿子安排上警卫，即 $d$；

（2）如果至少有一个儿子 $f[y][1]<f[y][2]$ ,即众多儿子中至少有个已经安排了警卫，$d$ 此时为 $0$；

3.$f[x][2]$：$x$ 安排了警卫，$x$ 的儿子$y$ 可以安排警卫，也可以被 $y$ 的儿子看守，还可以被父亲看守，则：

$f[x][2]=h[x]+ \sum min(f[y][0],f[y][1],f[y][2])$

$ans=min(f[root][1],f[root][2])$,$root$ 没有父亲

时间复杂度 $O(n)$

参考代码：点击

例4.P2015 二叉苹果树

题意简化，给定一棵带边权二叉树，去掉一些边（对应子树也会去掉）后，保留给定边数的情况下所形成的二叉树，使得二叉树边权和最大。

【思路点拨】

• 思路$1$：

本题可以将保留边转化为保留点，如果要保留 $q$ 条边，就是保留 $q+1$ 个点。 对于任意一个节点 $u$，二叉树是由左右子树构成的，那么可以定义 $f[u][k]$ 表示以 u 为根的子树中保留 $k$ 个节点的最大权值和，设 $l[u]$、$r[u]$ 分别是 $u$ 的左、右儿子。

(1)定义状态：

$f[u][k]$ 表示以 $u$ 为根的子树中最多保留 $k$ 个节点的最大权值

(2)状态转移方程如下：

$f[u][k]=\max(f[l[u]][i]+f[r[u]][k-i-1]+a[u])(0 \leq i \leq k-1)$

(3)初始化（边界）

$f[u][0]=0$

$f[u][k]=a[u](k \not=0,u为叶子即l[u]=0,r[u]=0)$

(4)$answer=f[1][q+1]$

这种方法，容易想到，但是如果题目中是多叉树怎办？一种解决方法可以将多叉树转成二叉树，感兴趣可以尝试，我们看看这种问题的一般求解思路。

---

树上背包问题

对于这种问题，就是在树上最多保留 $q$ 个点或者边，相当于规定了某一个维度上的资源上限，使得整颗子树获得最优目标收益，这就是典型的树上背包问题。

设 $f[u,i,k]$ 表示以 $u$ 为根的子树中，已经遍历了 $u$ 号点的前 $i$ 棵子树，选了 $k$ 个节点的最优收益。

转移过程结合了树形 Dp 和背包 Dp 的特点，枚举 $u$ 点的每一个子节点 $v$，同时枚举以 $v$ 为根的子树选了几个节点，将子树的结果合并到 $u$ 上。

设节点 $v$ 的儿子个数为 $Sv$ ，以 $v$ 为根的子树大小为 $size_v$，可以得到转移方程：

$f[u][i][k]=\max_{j \leq min(size_v,k)}(f[u][i-1][k-j]+f[v][Sv][j])$

直接定义三维会超时，计算 $(u,i,k)$ 状态的值，用到了 $(u,i-1,k-j)$ 的值，那可以压缩一维，将 $i$ 这一维压行压掉，$k$ 这一维就必须从大到小（与$01$背包同理）。

(1)定义状态

$f[u][k]$ 表示以 $u$ 为根最多保留 $k$ 个节点，所能获得的最大收益

(2)状态转移方程：

$f[u][k]=max_{j\leq k}(f[u][k-j]+f[v][j])$

注意转移时$k$这一维必须从大到小。

(3)边界

$f[u][0]=0$

$f[叶子][1~q]=a[叶子]$

(4)$answer=f[root][q]$

• 思路2：

设 $f[u][k]$ 表示 $u$ 的子树上保留 $k$ 条边，至多保留的苹果数目

那么状态转移方程也就显而易见了

$f[u][k]=max( f[u][k], f[u][k-j-1]+f[v][j]+dis[u][v] )$

$u$ 表示当前节点，$v$ 是 $u$ 的一个子节点

想想为什么是 $f[u][k−j−1]$ 而不是 $f[u][k−j]$？(tips:由于定义状态 $k$ 为保留边数，$u$ 到 $v$ 还要使用一条边,当然本题依然将保留边转化为保留点)

参考代码：

版本1

版本2(链式)

例5.2014 [CTSC1997]选课

【题目大意】

现在有 $n$ 门课程，第 i 门课程的学分为 $a_i$，每门课程有零门或一门先修课，有先修课的课程需要先学完其先修课，可能学习该课程。

一位学生要学习 $m$ 门课程，求其能获得的最多学分数。$(n,m \le 300)$

【思路点拨】

某一门课的先修课，可以看做父亲节点，要选择这门课程就必须选择父亲节点。

典型的树形背包 $Dp$ ，每门课的先修课最多只有一门（对应着树中每个节点至多只有 $1$ 个父亲），所以这 $N$ 门课构成了森林，可以新建一个“虚拟课程”- $0$ 号节点，把包含$N$ 个节点的森林转化为包含 $N+1$ 个节点的树，其中节点 $0$ 为根节点。

设 $F[u][k]$ 表示以 $u$ 为根的子树中选$k$门课能够获得的最高学分

$F[u][k]=max(F[u][k],F[v][j]+F[u][k-j])$

这是优化后背包，$k$ 就必须从大到小

最终答案是 $F[0][m+1]$

```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> G[1010];
int a[1010],f[1010][1010];
void dfs(int u){
    f[u][0]=0;
    f[u][1]=a[u];
	for(auto v:G[u]){
		dfs(v);
		for(int j=m;j>1;j--)  //复杂度不优秀
			for(int k=1;k<j;k++)
				f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
		}
}
int main(){
	cin>>n>>m;
	m++;
	for(int i=1;i<=n;i++){
		int u;
		cin>>u>>a[i];
		G[u].push_back(i);
	}
	dfs(0);
	cout<<f[0][m];
	return 0;
}

复杂度是 $O(n*m^2)$ ,可以进行上下界优化，复杂度优化到 $O(n*m)$.

树上背包优化

实际合并子树，并不需要 $j$ 每次都从 m 开始，$j$ 实际就是前面子树的大小，逐渐增加，那么可以用 siz 数组逐渐合并子树，时间复杂度是 $O(n*m)$ ,详细证明请参考 树上背包复杂度证明

U53204 【数据加强版】选课

需要使用 vector,否则会 MLE

参考代码如下：

#include<bits/stdc++.h>
using namespace std;

int n,m;
vector<vector<int> > G;
vector<vector<int> > f;
vector<int>a,siz;


void dfs(int u){
    f[u].resize(m+1);  //扩展u的大小

    f[u][0]=0;
    f[u][1]=a[u];
    siz[u]=1;
	for(auto v:G[u]){
        
		dfs(v);
        siz[u]+=siz[v];

		for(int j=min(m,siz[u]);j>1;j--)  //复杂度 O(nm)
			for(int k=1;k<=min(j-1,siz[v]);k++)
				f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]);
		}
}
int main(){
	cin>>n>>m;
	m++;
    G.resize(n+1); a.resize(n+1);
    f.resize(n+1); siz.resize(n+1);

	for(int i=1;i<=n;i++){
		int u;
		cin>>u>>a[i];
		G[u].push_back(i);
	}
	dfs(0);
	cout<<f[0][m];
	return 0;
}

例6.1273 有线电视网

题意简化，给定一棵带边权的树（边权是代价），叶子节点带点权（收益），保证不亏损的前提下，保留叶子节点越多越好。

思路点拨：

保留叶子结点的数量，维护总代价，如果这个代价大于零，就满足要求，那么找到最大保留叶子节点数量（总代价为正）就可以了。

定义 $f[u][j]$ 表示以 $u$ 为根，有 $j$ 个叶子节点，所能获得的最大价值。

显然转为为了树上背包问题

$f[u][j]=max(f[u][j-k]+f[v][k]-dis(u,v))$

$j$ 要从大到小枚举。 最后 $i$ 从大到小枚举，第一个 $f[1][i]$ 大于零时，输出 $i$，就是答案。

参考代码：点击

例7.P1272 重建道路

例8.P4516 [JSOI2018]潜入行动

例9.P3177 [HAOI2015]树上染色

---

换根Dp

树形Dp中换根问题又被称为二次扫描，通常不会指定根结点，并且根结点的变化会影响一些值，例如子结点深度和、点权和等。

对于这种问题，如果暴力枚举每一个点作为根，算法复杂度太高，仔细分析，将根节点与其一个子节点转化的过程中，某些值是可以保留的，不要重头开始算，这个过程就是“换根”。 通常进行两次 $DFS$，第一次 $DFS$ 预处理诸如深度、点权和等信息，第二次 $DFS$ 开始进行换根动态规划。

例10.P10974 Accumulation Degree

题意简化：给你一颗树，每条边有一个最大容量，根结点可以流出无限的流，叶子结点可以接受无限多的流，其他结点不储存水。

思路点拨：

首先考虑朴素算法：枚举源点$s$，计算以此点为源所能流出的最大流量。 如把$s$当做树根，整个水系成为有根树，河道的方向也确定了。根节点流向子树，子树与原问题结构相似，此问题就是一个树形$DP$。

设$D[x]$表示以$x$为根的子树中，把$x$作为源点，从$x$出发流向子树的流量最大是多少。

$D[x]=\sum \left\{\begin{matrix} min(D[sonx],edge[x][sonx]),sonx度>1(sonx不是叶子) \\edge[x][sonx],sonx度=1（sonx是叶子） \end{matrix}\right. $

若$s$为树根，$D[s]$就是从s流出的最大流量，也就是整个树的最大流出流量，枚举每一个结点作为根，此时算法复杂度是$O(n^2)$

优化：用“二次扫描换根法”代替源点的枚举，可以在$O(N)$的时间内解决整个问题。

总体思路是：选一个点作为根节点（一般是第一次扫描的根），计算出此点作为整个树根的值，从这个点推算出其儿子作为整个树的根的值。

设$F[x]$表示把$x$作为整个树的根，流向整个水系，流量最大是多少？ 那么$F[root]=D[root]$

也就是现在$F[x]$已经求出，考虑其子节点$y$，$F[y]$尚未被计算。

$F[y]$包含两部分：

• 1.从$y$流向以$y$为根的子树的流量，已经计算并保存在$D[y]$中。

• 2.从$y$沿着父节点$x$的河道，进而流向水系中其他部分。

把$x$作为源点，总流量是$F[x]$，从$x$流向$y$的流量为$min(D[y],edge[x][y])$,那么从$x$流向除$y$以外其他部分的流量就是二者之差 $F[x]-min(D[y],edge[x][y])$,那么$y$如果作为源点，$y$流向$x$的流量就是$min(F[x]-min(D[y],edge[x][y]),edge[x][y])$。当然，$x$如果度为$1$，需要特殊判断。

$ F[y]=D[y]+\sum \left\{\begin{matrix} min(F[x]-min(D[y],edge[x][y]),edge[x][y]),x度>1(x不是叶子) \\edge[x][y],x度=1 \end{matrix}\right.$

第二次扫描与换根：原根值已经算完，将儿子作为树根，计算此时的值。

参考代码：点击

例11.P3478 [POI2008]STA-Station

思路点拨：

暴力枚举根节点，以某一个点作为树根，$d[x]$表示$x$点的深度，$DFS$整颗树，计算所有结点的$d[x]$，累加$d[x]$，找到深度和最大值对应的树根。

设$x$的儿子$y$，$x$若为整个树的树根，当$y$变成树根时，整个树节点深度和增加$n-size[y]$（$size[y]$表示以$y$为根的子树的大小），减少$size[y]$。

那么第一次$dfs$，计算出$d[x]$、$size[x]$，设$f[x]$表示以$x$为整个树根的深度和，第一次$dfs$，也可以计算出$f[root]$ 。 第二次$dfs$，若$x$的儿子为$y$，$x$为根，换做$y$做根，$f[y]=f[x]-size[y]+n-size[y]=f[x]+n-2*size[y]$。

参考代码：点击

例12. CF1187E Tree Painting

题意简化:给定一棵$n$个点的树，初始全是白点，要求你做$n$步操作，每一次选定一个与一个黑点相隔一条边的白点，将它染成黑点，然后获得该白点被染色前所在的白色联通块大小的权值。第一次操作可以任意选点。求可获得的最大权值

思路点拨：

设$f[x]$ 表示以$x$为子树根，子树获取的权值

$g[x]$ 表示以$x$为整棵树的根，所能获取的最大值

$f[x]=size[x]+\sum_{i \in sonx}f[i]$

以$1$作为树根，$g[1]=f[1]$,枚举其他节点求$g[x]$,复杂度是$O(n^2)$,采用二次扫描换根优化。

即$g[x]$已经算出，求$g[y]$。

$g[y]=n+\sum f[sony] + n-size[y]+ \sum_{i \in sonx |i \not=y}f[i]$

$=n+(f[y]-size[y])+n-size[y]+\sum_{i\in sonx |i\not= y}f[i]$

=$n+n-2*size[y] + \sum_{i \in sonx |i \not= y}f[i] +f[y] $

$=n+n-2*size[y]+ \sum_{i \in sonx }f[i]$

$=n+n-2*size[y]+g[x]-n$

$=g[x]+n-2*size[y]$

参考代码：点击

P3525 [POI2011]INS-Inspection

luogu题目翻译有问题，题意如下：

一棵$n$个节点的树，行动中心$S$从$1->N$依次选择。

从$S$出发前往任意一个未标记到的点(沿树上两点的唯一路径走)，标记该节点，然后返回$S$。相邻两次行动所经过的道路不允许有重复，最后一次标记后不需要返回，求路程总和的最小值。

第$i$行输出行动中心为$i$时的答案，如果不可能则输出$-1$

思路分析：

根据题意，如果以$i$为根，要求相邻两次行动所经过的道路不重复，也就是$i$的最大子树不能超过$n/2$，因为超过以后其他子树点都访问完后，这颗最大子树还有多余2个节点没有访问，必然出现相邻两次行动走重复道路的情况。

简单证明：如果$n$个节点的树最大的子树为$y$，其余子树大小之和为$x$,$x+y=n-1$,当$y-x>=2$时，无法实现“相邻两次行动所经过的道路不重复”，$y>=(n+1)/2$，那么$y<=n/2$。

也就是说当节点$i$为重心时，才有解，否则输出$-1$；

最终答案就是: $2*\sum d[i]-max(d[j])$,$d[i]$表示从根节点到i的距离,由于折返，所以乘以$2$，最后停在$j$，少走$d[j]$,当然需要停在距离根节点最远的节点j上，这样走过距离最小。

不过这里有一个特殊情况，当$n$为偶数，例如$n=10$,有两颗子树，一颗为$5$，一颗为$4$,最后只能停在$5$这颗子树上，但是$5$这颗子树不一定是最远距离，也就是要去$5$这颗子树距离根的最远距离，然后减掉。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
vector<int>e[N];
int n,dep[N],siz[N],fa[N];
bool core[N];
long long ans;int maxlong;
int d[N];  //d[x] 表示以x为根的子树中距离x最远的距离 
void dfs(int x,int father)
{
	dep[x]=dep[father]+1;
	siz[x]=1;
	fa[x]=father;
	for(int j=0;j<e[x].size();j++)
	{
		int y=e[x][j];
		if(y==father)continue;
		dfs(y,x);
		siz[x]+=siz[y];			
	}
}
bool check(int x)
{
	if(n-siz[x]>n/2)return false;
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(y==fa[x])continue;
		if(siz[y]>n/2)return false;		
	}
	return true;
}
void dfs2(int x,int father)
{
	dep[x]=dep[father]+1;
	maxlong=max(maxlong,dep[x]-1);
	ans+=dep[x]-1;
	d[x]=0;
	siz[x]=1;
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(y==father)continue;
		dfs2(y,x);
		d[x]=max(d[x],d[y]+1);
		siz[x]+=siz[y];
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}	
	dfs(1,0);	
	
	for(int i=1;i<=n;i++)
		if(check(i))
			core[i]=1;
	
	
	for(int i=1;i<=n;i++)
		if(core[i])
		{
			ans=maxlong=0;
			dep[0]=0;
			dfs2(i,0);
			for(int j=0;j<e[i].size();j++)
			{
				int y=e[i][j];
				if(siz[y]==n/2)
				{
					maxlong=d[y]+1;
					break;
				}
			 } 
			printf("%lld\n",ans*2-maxlong);
		}
				
		else
			printf("-1\n");
			
	return 0;
}

P3574 [POI2014] FAR-FarmCraft

题意：

给定一棵$n$个节点的树，访问每一个节点，给每个节点发一台电脑，节点安装电脑需要$c_i$的时间，访问完节点，就会离开，节点有人自己安装电脑，最后回到节点$1$。询问如何发电脑，使得所有节点安装完电脑所用时间最短。

思路分析：

设$f[x]$表示以$x$为根的树，所有节点安装完电脑所用的最短时间。

运送电脑路上所花的时间实际上是固定的，主要是送到后节点还需要安装，还需要等待，关键点就成了如何安排运送顺序使得$f[x]$最小。

对于一般情况，我们可以得到状态转移方程：

$f[x]=max(f[x],siz[x]+1+f[y]$,$y$是$x$的儿子，其中$siz[x]$表示访问$y$之前所走的时间。含义如下图：

注意：$siz[x]$表示访问$y$之前路上花的时间,从$x$到$y$花$1$的时间,$f[y]$以$y$为根的子树完成的最短时间，肯定会比$siz[y]$大。

结果与子树遍历顺序有关，可以用微扰法找到排序的关键字。

如果先访问$y$，访问$z$，可以得到

$f_1[x]=siz[x]+max(1+f[y],2+siz[y]+1+f[z])$

如果交换，可以得到

$f_2[x]=siz[x]+max(1+f[z],2+siz[z]+1+f[y])$

交换前更优，等价于$f_1[x]<f_2[x]$

即$max(1+f[y],2+siz[y]+1+f[z])<max(1+f[z],2+siz[z]+1+f[y])$

$max(f[y],2+siz[y]+f[z])<max(f[z],2+siz[z]+f[y])$

由于$f[y]<2+siz[z]+f[y],f[z]<2+siz[y]+f[z]$

上式等价于$2+siz[y]+f[z]<2+siz[z]+f[y]$

即：$f[z]-siz[z]<f[y]-siz[y]$

也就是$f[y]-siz[y]$越大，应该早访问，对于每一个节点$x$,其所有儿子节点$f[y]$确定后，按照关键值$f[y]-siz[y]$从大到小排序,从而获得访问顺序。

参考代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,c[N];
vector<int>e[N];
int f[N],siz[N];
bool cmp(int y,int z)
{
	return f[y]-siz[y]>f[z]-siz[z];
}
void dfs(int x,int fa)
{
	f[x]=c[x];
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(y==fa)continue;
		dfs(y,x);
	}
	sort(e[x].begin(),e[x].end(),cmp);
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(y==fa)continue;
		f[x]=max(f[x],siz[x]+f[y]+1);
		siz[x]+=siz[y]+2;
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",c+i);
	for(int i=1;i<n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		e[b].push_back(a);
	}
	dfs(1,0);
	int ans=max(f[1],siz[1]+c[1]);
	printf("%d",ans);

	return 0;
}

---

学习完毕

{{ select(1) }}

• YES
• NO