[换根dp] Codeforces Round 67 (Rated for Div. 2) E

题意：给定一颗树，第一次选一个点涂黑，贡献是与当前点相连的白点数量（联通分量），剩下每次只能选与黑点相邻的白点，直到整棵树涂黑，问最大能贡献多少

考虑问题本质，相连的白点就是子树大小，不管选择方式如何只要根固定了答案是唯一的。

并且考虑维护子树大小数组，可以发现对于根与根相邻的两点间子树大小非常好转移 （总数固定，另一个点的儿子数也知道）

所以可以二次扫描对每个点做根重新转移统计答案即可

详细见代码：

/*
    Zeolim - An AC a day keeps the bug away
*/
 
//#pragma GCC optimize(2)
//#pragma GCC ("-W1,--stack=128000000")
#include <bits/stdc++.h>
using namespace std;
#define mp(x, y) make_pair(x, y)
#define fr(x, y, z) for(int x = y; x < z; ++x)
#define pb(x) push_back(x)
#define mem(x, y) memset(x, y, sizeof(x))
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef std::pair <int, int> pii;
typedef std::vector <int> vi;
//typedef __int128 ill;
const ld PI = acos(-1.0);
const ld E = exp(1.0);
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 386910137;
const ull P = 13331; 
const int MAXN = 1e6 + 10;

struct node { int x, y; };
vector <int> edge[MAXN];
ll scnt[MAXN] = {0}, ans[MAXN] = {0};
int used[MAXN] = {0};

void gao(int now) //对根1进行统计子数大小和贡献 
{
	used[now] = 1;
	for(auto x : edge[now])
	{
		if(!used[x])  
		{
			gao(x);
			scnt[now] += scnt[x];
		}
	}
	++scnt[now];
	ans[1] += scnt[now];
}

void chanrot(int now, int fa) //换根 
{
	for(auto x : edge[now])
	{
		if(x != fa)
		{
			ans[x] = ans[now] - scnt[x] - scnt[now]; //将根从now换到x 
			int xcnt = scnt[now] - scnt[x];
			scnt[x] = scnt[now];
			scnt[now] = xcnt;
			ans[x] += scnt[x] + scnt[now];//统计贡献 
			chanrot(x, now);
			xcnt = scnt[x] - scnt[now];//将根换回去供下次计算 
			scnt[now] = scnt[x];
			scnt[x] = xcnt;
		}
	}
}
int main()
{  
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("d:out.txt","w",stdout);
    //freopen("d:in.txt","r",stdin);
	int n;
	cin >> n;
	for(int i = 0, x, y; i < n - 1; ++i)
	{
		cin >> x >> y;
		edge[x].pb(y);
		edge[y].pb(x);
	}
	gao(1);
	chanrot(1, 0);
	ll rans = 0;
	for(int i = 1; i <= n; ++i)
		rans = max(rans, ans[i]);
	cout << rans << '
';
    return 0;
}