题解 P3478 【[POI2008]STA-Station】

换根DP板子题
先以一个节点作为根统计一下子树大小，然后dfs更新每个节点作为根的答案
时间复杂度$O(n)$

#include<iostream>
#include<vector>
#define int long long
using namespace std;
vector<int> g[1000005];
int sum[1000005],s,ans,n,pp=1;
void dfs1(int u,int f,int d){
	sum[u]=1;
	s+=d;
	for(int i=0;i<g[u].size();i++){
		if(g[u][i]==f)continue;
		dfs1(g[u][i],u,d+1);
		sum[u]+=sum[g[u][i]];
	}
}
void dfs2(int u,int f){
	for(int i=0;i<g[u].size();i++){
		if(g[u][i]==f)continue;
		int v=g[u][i];
		int rs=s,ru=sum[u],rv=sum[v];
		s=s+n-2*sum[v];
		sum[u]-=sum[v];
		sum[v]=n;
		if(s>ans){
			ans=s;
			pp=v;
		}
		dfs2(v,u);
		s=rs;
		sum[u]=ru;
		sum[v]=rv;
	}
}
signed main(){
	int u,v;
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs1(1,0,0);
	ans=s;
	dfs2(1,0);
	cout<<pp;
	return 0;
}