换根DP

简介

换根DP是树形DP的一个分支，它的转移方式和普通的树形DP不完全一样。

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

通常需要两次DFS，第一次DFS（自底向上）预处理诸如深度，点权和之类的信息，在第二次DFS（自顶到底）开始运行换根动态规划。

典型例题：P3478（经典换根DP） P2986 CF1187E

从上面几个题可以看出来换根DP解决的基本问题是：

对一个无根树，指定某个结点为根时求某些极值。一般和点权和以及边权和有关。

换根DP的基本思想：

首先指定一个根结点，用一次普通树形DP的方法求出该点为根时的值。

再利用换根的方法，每次将根变成相邻的结点，看这个值的变化量，进行递推求解。

堂上练习：P3478（例题，一定要会写） CF1092F（P2986的简化，但数据范围加大） CF1324F（有点思维难度）

其他习题：P3047 POJ3585

例题

1. [POI2008] STA-Station

本题是换根DP的入门题。

分析

第一步：先指定一个根结点，不妨设为1号结点。

第二步：进行一次DFS，求出g[i]=以i为根的子树的所有结点的深度和。

这一步方程很简单，g[i]=sum(g[j])+size[i]，j是i的儿子，size是子树大小。

解释是显然的，对于i的每个儿子j，以j为根的这个子树在以i为根的子树中，深度都会自动增加1，所以最后要加上size[j]。而由于i结点本身要计算，所以sum(size[j])+1=size[i]，直接在DFS时顺便处理出来就可以了。

那么，这个时候的g[1]就是1号结点为根时所有结点的深度和。记dp[i]=以i为根时所有结点的深度和，则dp[1]=g[1]。

第三步：进行换根。

对于样例，size[1]=8，size[4]=7。

当根结点从1号结点变成4号结点时，可以发现，4号结点和它的子树的深度都减少了1，4号结点子树以外的结点的深度都增加了1。

所以，dp[4]=dp[1]-size[4]+(n-size[4])=dp[1]+n-2*size[4]。

由于dp[1]=g[1]=18，所以可以直接推出dp[4]=12。

将该式推广到一般情况，就有：

若u是v的父亲，则有dp[v]=dp[u]+n-2*size[v]。

直接用该式从顶到底转移即可。

等下，这个g数组好像不需要啊。。。

因此最终算法是：

第一次dfs处理出size数组和dp[1]=g[1]，第二次dfs处理出所有dp，然后遍历dp数组找到最大值所在的最小编号结点即可。

记得开long long。

2. [USACO10MAR] Great Cow Gathering G

一道典型的换根DP，思路和上一题一样。

# include<iostream>
using namespace std;
# define ll long long

const int N=1e5+10;
int n,c[N],a,b;
int cnt,head[N],to[2*N],nxt[2*N],son[N];
ll l,val[2*N],dp[N],ans;

void add(int a,int b,ll l){
	to[++cnt]=b;
	val[cnt]=l;
	nxt[cnt]=head[a];
	head[a]=cnt;
}

void f(int x,int fa){
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
		ll w=val[i];
		f(y,x);
		son[x]+=son[y];
		dp[x]+=son[y]*w+dp[y];
	}
	son[x]+=c[x];
}

void dfs(int x,int fa){
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(y==fa) continue;
		ll w=val[i];
		dp[y]=dp[x]-son[y]*w+(son[1]-son[y])*w;
		dfs(y,x);
	}
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i) cin>>c[i];
	for(int i=1;i<n;++i){
		cin>>a>>b>>l;
		add(a,b,l);
		add(b,a,l);
	}
	f(1,0);
	ans=dp[1];
	dfs(1,0);
	for(int i=2;i<=n;++i) ans=min(ans,dp[i]);
	cout<<ans;
	return 0;
}

3. Tree painting

题面

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

输入：第一行点数n，后面n-1行每行两个正整数代表一条树边。

输出：一个正整数表示最大权值。

数据范围：$n\le 2\times 10^5$。

分析

首先要证明一个性质：答案只和第一个选定的黑点有关，和后面涂黑点的顺序无关。

证明是简单的：涂黑第一个点之后，以该黑点为根，整个树被分成了若干个子树，而从子树开始涂黑时，也必然是从根开始涂黑，且子树之间的涂黑结果互相独立。

于是，一个点的贡献来源于以它为根的子树和它的祖先中能达到的白点数。当这个点的父亲已被染成黑色，该点的祖先颜色已无法对该点贡献造成影响，只与子树有关，而子树不受顺序影响。 所以答案与除第一次选点顺序无关。

从刚刚的证明过程中，我们可以知道，如果令第一次涂黑的点为根结点，那么每个点的贡献来源于以它为根的子树和它的祖先中能达到的白点数，即它的深度。

因此，问题变成了：找到一个点，使得以它为根时，树上所有点的深度和最大。

这就是P3478。