E. Tree Painting(换根dp)_e tree painting

题目链接

题意：给你一颗树，一开始树的结点都是白色的。开始染色，一开始你可以将任意一个白色结点染成黑色，随后只能给黑色结点旁边的白色结点染色，每次染色能获得与这个结点联通的所有白色结点积分数。问怎样染色可以使积分数最多。

题解：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+100;
vector<int>e[N];
int n;
ll sz[N],dp[N],ans;
void dfs1(int u,int fa){
	sz[u]=1;
	for(int i=0;i<e[u].size();++i){
		int v = e[u][i];
		if(v==fa) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		dp[u]+=dp[v];
	}
	dp[u]+=sz[u]; 
}
void dfs2(int u,int fa){
	ans=max(ans,dp[u]);
	for(int i=0;i<e[u].size();++i){
		int v = e[u][i];
		if(v==fa) continue;
		ll res = dp[u] - sz[v] - dp[v];
		dp[v] = dp[v] + res + (n-sz[v]);
		dfs2(v,u);
	}
}
int main()
{
	cin>>n;
	for(int i=1;i<n;++i){
		int u,v;
		cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);		
	}
	dfs1(1,0);
	dfs2(1,0);
	cout<<ans<<endl;
}