Educational Codeforces Round 67 (Rated for Div. 2) E. Tree Painting

题目链接
大意：给你一颗树，第一次选一个点染黑，之后从与黑点连接的白点中选点涂黑，问最大价值是多少？
价值定义：每次选择涂的点可获得这个点的联通块大小的价值，简而言之就是，将黑点看为根的话，那么当前点的子树的节点数即为价值。
思路：考虑换根 $dp$dp，先以 $1$1为根，预处理每个点的子节点数目和染某个点的价值和。很显然，答案只与第一个点有关，与染的顺序无关，所以我们要考虑的就是每个点为第一次染的点的最大值。那么显然我们可以换根来解决。
在 $dfs$dfs过程中，假设当前点为 $now$now，遍历到一个子节点为 $k$k，那么我们将根转化成 $k$k，所需要改变的是当前根的子节点个数和，新根的子节点个数和，当前根的价值和，新根的价值和。
设 $a$a数组为子节点个数和， $b$b数组为价值和.那么需要两步，四个公式即可。
1.断开新旧根的连接
2.重连新旧根
$1.b\left[now\right]=b\left[now\right]-b\left[k\right]-a\left[k\right]$1.b[now]=b[now]−b[k]−a[k]旧根的价值去掉新根的价值。
$2.a\left[k\right]=a\left[k\right]+a\left[now\right]-a\left[k\right]+b\left[now\right]$2.a[k]=a[k]+a[now]−a[k]+b[now]新根的价值加上更新后的旧根的价值
$3.a\left[now\right]-=a\left[k\right]$3.a[now]−=a[k]旧根的子节点数去掉新根的子节点数
$4.a\left[k\right]+=a\left[now\right]$4.a[k]+=a[now]新根的子节点数加上更新后的旧根的子节点数
之后再回溯回来即可

#include<bits/stdc++.h>
 
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
using namespace std;
 
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
LL b[N],a[N],ans;
vector<int>v[N];
int n;
void dfs(int now,int pre){
	a[now]=1;
	for(auto k:v[now]){
		if(k==pre)continue;
		dfs(k,now);
		a[now]+=a[k];
		b[now]+=b[k];
	}
	b[now]+=a[now];
	return ;
}
void cg(int A,int B){
	b[A]=b[A]-b[B]-a[B];
	b[B]=b[B]+b[A]+(a[A]-a[B]);
	a[A]-=a[B];
	a[B]+=a[A];
}
void bfs(int now,int pre){
	ans=max(ans,b[now]);
	for(auto k:v[now]){
		if(k==pre)continue;
		cg(now,k);
		bfs(k,now);
		cg(k,now);
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<n;i++){
		int s,t;
		cin>>s>>t;
		v[s].pb(t);
		v[t].pb(s);
	}
	dfs(1,0);
	bfs(1,0);
	cout<<ans<<endl;
	return 0;
}