从根到叶,再从叶回到根,总是在返回时收集子树的信息,从小到大更新每个节点的信息就是在树上的DP。
树的中心
给定一棵树,树中包含$n$个结点(编号$1-n$)和 $n−1$ 条无向边,每条边都有一个权值。请你在树中找到一个点,使得该点到树中其他结点的最远距离最近。
很容易想到用dp(i)
表示i
到其它点的最远距离。但是问题是如果我们将无根树转化为有根树,我们就只能记录每一个节点向下走的最远距离,为了得到每一个点到其他点的最远距离我们需要做$n$次dfs,时间复杂度为$O(n^2)$,这种算法会导致大量的无效计算。
我们采用做两次dfs的方法,第一次记录i
向下走的最长距离和次长距离,第二次再记录i
向上走的最长距离,两个方向中取 $Max$ 即为该点到其他节点的最长距离。
d1[i]
记录i
点向下走的最长距离,d2[i]
记录i
点向下走的次长距离。up[i]
记录i
点向上走的最长距离。
我们对每一个点向上回溯,对于向上的最长距离分析有两种可能
1.如果点j在父节点i的最长路径上,那么up[j] = max(up[i],d2[i])
;
2.如果点j不在父节点i的最长路径上,那么up[j] = max(up[i],d1[i]);
// 第一次dfs 先求出向下的最长和次长距离并记录
int dp(int root){
vis[root] = true;
for(int i = h[root]; i != -1; i = ne[i]){
int j = e[i];
if(vis[j])continue;
int d = dp(j) + w[i];
if(d >= d1[root])d2[root] = d1[root], d1[root] = d;
else if(d > d2[root])d2[root] = d;
}
return d1[root];
}
memset(st,false,n + 1);
// 第二次dfs 求up[i]
void dup(int root){
vis[root] = true;
for(int i = h[root]; i != -1; i = ne[i]){
int j = e[i];
if(vis[j])continue;
if(d1[root] == d1[j] + w[i])up[j] = w[i] + max(up[root],d2[root]); // 如果在最长路上,那么向上走的最长路可能是向上再向上或向上再向下走次长路
else up[j] = w[i] + max(up[root],d1[root]); //如果不在最长路上,那么就是向上走的最长路和向下走的最长路中选一条最长的
dup(j);
}
}
注意递推顺序!!
和其他形式的动态规划一样,我们要确认递推顺序确保任何计算依赖的结果已经被提前计算出。
对于第一次dfs,我们需要子节点的结果来计算父节点,因此先进行dfs再计算。
对于第二次dfs,我们需要父节点的结果来计算子节点,因此先计算再进行dfs。
树的最大独立集
对于一棵$n$个结点的无根树,选出尽量多的结点,使得任何两个结点
均不相邻(称为最大独立集),然后输入$n-1$条无向边,输出一个最大独立集。
$eg.$ 没有上司的舞会
f[i][1]
表示以i为根节点的子树的最大独立集的大小并选择i,f[i][0]
表示以i为根节点的子树的最大独立集的大小并且不选择i。
void dp(int root){
f[root][1] = happy[root]; // 选择root则最大独立集中一定包含了root的信息
for(int i = h[root]; i != -1; i = ne[i]){
int j = e[i];
dp(j);
f[root][1] += f[j][0]; // 由于选择了root,root的所有邻接点就不能选择
f[root][0] += max(f[j][0],f[j][1]); // 如果不选择root,就从选择或者不选择邻接点中挑出一个最大值
}
}
最终答案为max(f[root][1],f[root][0])
树的重心
树的重心(质心)。对于一棵$n$个结点的无根树,找到一个点,使得把树变成以该点为 根的有根树时,最大子树的结点数最小。换句话说,删除这个点后最大连通块(一定是树)的结点数最小。
dp(i)
表示以i
为根的子树的节点数,当去掉i后连通块有两种存在的方式,一种是i
向下走的每一株子树(以i
的所有邻接点j为根的子树),一种是i
向上的所有节点构成的一株子树(显然这株子树是唯一的,节点数为n - dp(i)
)。
int dp(int root){
vis[root] = true;
int s = 1, t = 0; // s记录当前子树的总结点数,t记录root的所有子树中的最大节点数
for(int i = h[root)l i != -1; i = ne[i]){
int j = e[i];
if(vis[j])continue;
int d = dp(j);
s += d;
t = max(t,d);
}
res = min(res,max(n - s,t); // 用一个全局变量res来维护答案
return s;
}
树的最长路径
对于一棵$n$个结点的无根树,找到一条最长路径。换句话说,要找到两个点,使得它们的距离最远。
dp(i)
表示i到叶节点的最远距离,这是一个非常容易处理的dfs。对于这个问题我们要同时维护两个信息,从i
开始的最长路径d1
和次长路径d2
,两者相加就是经过i的最长的路径,我们再从经过所有点的最长路径中选择最长的,就是树上的最长路径。
int dp(int root){
vis[root] = true;
int d1 = 0, d2 = 0;
for(int i = h[root]; i != -1; i = ne[i]){
int j = e[i];
if(vis[j])continue;
int d = w[i] + dp(j);
if(d >= d1)d2 = d1, d1 = d; // 处理最长路径和次长路径
else if(d > d2)d2 = d;
}
res = max(res,d1 + d2); // 依然是用一个全局变量res来维护答案
return d1;
}