技术经验分享：CF1187ETreePaiting（树形DP+换根）

"

CF1187E Tree Painting（树形DP+换根）

题意：

给出一棵树，开始所有的点都是白色的，你可以给树上的点染色。

一次染色，你可以选择任意一个和已经被染成黑色的点相邻的白点，将其染成黑色，并获得等同于这个点所在的白色连通块的点数的分数。询问最大分数。

题解：

先一遍DFS处理出每个点的子树节点数量，第二遍DFS不断更换根节点，维护当前所有子树节点数量和，取最大的就是答案。

//第一步选择一个白色顶点涂成黑色

//之后每//代码效果参考：https://v.youku.com/v_show/id_XNjQwNjg1NTU4OA==.html

//每涂一次的分数是这个点所在的白色连通块的点数

//询问最大分数

#include

using namespace std;

const int maxn=2e5+100;

typedef long long ll;

int n;vector[span style=""color: rgba(0, 0, 255, 1)"">int

int size【maxn】;

void dfs (int u,int f) {

size【u】=1;

for (int v:g【u】) {

if (v==f) continue;

dfs(v,u);

size【u】+=size【v】;

}

}

ll sum,ans=0;

//换根

//从u转移到v

//size【u】变成n-size【v】

//size【v】变成n

void dfs1 (int u,int f) {

for (int v:g【u】) {

if (v==f) continue;

int t1=size【u】,t2=size【v】;

size【u】-=size【v】;

size【v】=n;

sum+=size【u】-t1+size【v】-t2;

ans=max(ans,sum);

//代码效果参考：https://v.youku.com/v_show/id_XNjQwMDQxMDA2NA==.html

sum-=size【u】-t1+size【v】-t2;

size【u】=t1;size【v】=t2;

}

}

int main () {

scanf(""%d"",&n);

for (int i=1;i

int x,y;

scanf(""%d%d"",&x,&y);

g【x】.push_back(y);

g【y】.push_back(x);

}

dfs(1,0);

for (int i=1;i<=n;i++) sum+=size【i】;

ans=sum;

dfs1(1,0);

printf(""%lld\n"",ans);

}