CF1534H 题解

发表于 更新于
比较复杂的交互形式的换根DP题

第一次 DP 的部分和后面交互的部分现有的两篇题解都讲的比较清楚了，这里注意补充解释一下换根和计算答案的部分，（让像我这样的菜鸡容易理解一点）。

我们先列出第一次 DP 的式子： \[ f_u=\max\limits_{i=0}^{size-1} f_v+i \] 那么我们考虑当前节点是 \(u\) ，新的根是 \(v\)，那么此时我们要抛弃掉 \(v\) 对 \(u\) 的贡献并且加入 \(fa_u\) 对 \(u\) 的贡献。考虑直接将与 \(u\) 相连的所有点按 \(f\) 值进行排序，那么每次的 \(v\) 将整个数组分割成一个前缀和一个后缀，式子其实就是上面那个式子，但是后缀部分的 \(i\) 要减去当前这个 \(v\) 所多算的 \(1\)。因此不需要什么平衡树，只用预处理前缀最大值、后缀最大值，中间再合并一下就好了。

计算答案的部分则是简单的分类讨论。我们在计算前仍然需要对所有儿子按 \(f\) 值排序。对于当前根是 \(u\) ，有 \(3\) 种情况：

  1. 询问的两个点分别在当前节点的两个不同子树内，则贡献为 \(\max f_{v0}+f_{vi}+i-1\)；
  2. 询问的两个点中有一个是当前根，则贡献为 \(f_{v0}+deg_u-1\)；
  3. 询问的两个点都是当前的根，则贡献为 \(deg_u\)。

放一下这个关键的 DFS 部分的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool cmp(int x,int y){
	return f[x]>f[y];
}
void dfs2(int u,int fa){
	sort(e[u].begin(),e[u].end(),cmp);
	for(int i=1;i<e[u].size();i++)maxm=max(maxm,f[e[u][0]]+f[e[u][i]]+i-1);
	maxm=max(maxm,max(f[e[u][0]]+(int)e[u].size()-1,(int)e[u].size()));
	pre[0]=suf[e[u].size()+1]=0;
	for(int i=0;i<e[u].size();i++)pre[i+1]=max(pre[i],f[e[u][i]]+i);
	for(int i=e[u].size()-1;i>=0;i--)suf[i+1]=max(suf[i+2],f[e[u][i]]+i);
	for(int i=0;i<e[u].size();i++){
		res[e[u][i]]=max(pre[i],suf[i+2]-1);
	}
	for(int i=0;i<e[u].size();i++){
		if(e[u][i]==fa)continue;
		f[u]=max((int)e[u].size()-1,res[e[u][i]]);
		dfs2(e[u][i],u);
	}
}