换根DP

又称二次扫描。

特征：

树中没有指定根节点。
采用不同的节点作为根，答案可能不一样。

模板

P3478 [POI2008] STA-Station

暴力解法：枚举根节点，求以该节点作为根时，所有节点的深度之和，时间复杂度O(n^2)
优化：直接通过父节点的深度之和，得到子节点的深之和：子节点变为根节点之后，子节点及其子树深度+1，其他节点深度-1。
解法：

先指定任意节点作根节点
搜索完成指定根的答案计算，得到指定根的解。
二次扫描，利用原来根的解推出每个节点作为根的解。

定义状态

dp[i]表示以1为总根节点，i为根的子树所有节点的深度之和
f[i]表示以i为总根节点，其他节点的深度之和。
答案：1~n中f[i]的最大值

求状态转移方程

dp[cur]+=dp[nxt]
f[cur]=f[fa]-siz[cur]+(n-siz[cur])
这个子树的深度全部-1，即减去这个子树的大小；其余节点深度+1（siz[i]为i的子树节点数量）

初始状态

dp[cur]=dep[cur]（dep[i]为节点i的深度）
f[root]=dp[root]

验证转移顺序

dp是先递归后转移
f是先转移再递归（f[nxt]=f[cur]-siz[nxt]+(n-siz[nxt])）

代码

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

const int N=1e6+5;
int n,dp[N],f[N],dep[N],siz[N];
vector<int>nbr[N];

void dfs(int cur,int fa)
{
	dp[cur]=dep[cur]=dep[fa]+1;
	siz[cur]=1;
	for(int i=0;i<nbr[cur].size();i++)
	{
		int nxt=nbr[cur][i];
		if(nxt==fa)
			continue;
		dfs(nxt,cur);
		dp[cur]+=dp[nxt];
		siz[cur]+=siz[nxt];
	}
	return ;
}

void second_dfs(int cur,int fa)
{
	for(int i=0;i<nbr[cur].size();i++)
	{
		int nxt=nbr[cur][i];
		if(nxt==fa)
			continue;
		f[nxt]=f[cur]-siz[nxt]+(n-siz[nxt]);
		second_dfs(nxt,cur);
	}
	return ;
}

signed main()
{
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		nbr[x].push_back(y);
		nbr[y].push_back(x);
	}
	dfs(1,0);
	f[1]=dp[1];
	second_dfs(1,0);
	int maxi=-1e9,pos;
	for(int i=1;i<=n;i++)
		if(f[i]>maxi)
		{
			maxi=f[i];
			pos=i;
		}
	cout<<pos;
	return 0;
}

时间复杂度O(n)

CF1187E Tree Painting(双倍经验)

只需将dep初值设为0即可

P2986 [USACO10MAR] Great Cow Gatrering G

本题加了边权和边权，只要稍微改动即可。
dfs与second_dfs代码：

void dfs(int cur,int fa)
{
	siz[cur]=val[cur];
	for(int i=0;i<nbr[cur].size();i++)
	{
		int nxt=nbr[cur][i].to,w=nbr[cur][i].w;
		if(fa==nxt)
			continue;
		dfs(nxt,cur);
		dp[cur]+=dp[nxt]+siz[nxt]*w;
		siz[cur]+=siz[nxt];
	}
	return ;
}
void second_dfs(int cur,int fa)
{
	for(int i=0;i<nbr[cur].size();i++)
	{
		int nxt=nbr[cur][i].to,w=nbr[cur][i].w;
		if(fa==nxt)
			continue;
		f[nxt]=f[cur]-siz[nxt]*w+(tot-siz[nxt])*w;
		second_dfs(nxt,cur);
	}
	return ;
}

CF219D Choosing Capital for Treeland

定义状态

dp[i]表示以1为总根节点，i为根的子树需要反转方向的次数
f[i]表示以i为总根节点，需要反转方向的次数
答案：f[i]的最小值

求状态转移方程

dp[cur]+=dp[nxt]+w
w0 -> f[nxt]=f[cur]+1
w1 -> f[nxt]=f[cur]-1

初始状态

f[1]=dp[1]

验证转移顺序

dp是先递归后转移
f是先转移再递归

代码

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

const int N=2e5+5;
struct Node
{
	int to;
	int w;
};
int n,dp[N],f[N];
vector<Node>nbr[N];

void dfs(int cur,int fa)
{
	for(int i=0;i<nbr[cur].size();i++)
	{
		int nxt=nbr[cur][i].to,w=nbr[cur][i].w;
		if(fa==nxt)
			continue;
		dfs(nxt,cur);
		dp[cur]+=dp[nxt]+w;
	}
	return ;
}

void second_dfs(int cur,int fa)
{
	for(int i=0;i<nbr[cur].size();i++)
	{
		int nxt=nbr[cur][i].to,w=nbr[cur][i].w;
		if(nxt<span style="font-weight: bold;" class="mark">fa)
			continue;
		if(w</span>0)
			f[nxt]=f[cur]+1;
		else
			f[nxt]=f[cur]-1;
		second_dfs(nxt,cur);
	}
	return ;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		nbr[x].push_back((Node){y,0});
		nbr[y].push_back((Node){x,1});
	}
	dfs(1,0);
	f[1]=dp[1];
	second_dfs(1,0);
	int mini=1e9;
	for(int i=1;i<=n;i++)
		mini=min(mini,f[i]);
	cout<<mini<<"\n";
	for(int i=1;i<=n;i++)
		if(f[i]==mini)
			cout<<i<<" ";
	return 0;
}