CF1187E Tree Painting 题解
题意：
给定一棵 $n$ 个节点的树，初始全是白点。
要求你做 $n$ 步操作：每一次选定一个与一个黑点相隔一条边的白点将它染成黑点，然后获得该白点被染色前所在的白色联通块大小的权值。第一次操作可以任意选点。
求可获得的最大权值。
输入格式：
The first line contains an integer $n$ — the number of vertices in the tree ( $2 \le n \le 2 \cdot 10^5$ ).
Each of the next $n - 1$ lines describes an edge of the tree. Edge $i$ is denoted by two integers $u_i$ and $v_i$ , the indices of vertices it connects ( $1 \le u_i, v_i \le n $ , $ u_i \ne v_i$ ).
It is guaranteed that the given edges form a tree.
输出格式：
Print one integer — the maximum number of points you gain if you will play optimally.
数据范围：
$2 \le n \le 2 \times 10^5$
注意到确定了一个点之后，后面选点都不会影响权值了。一眼丁真，鉴定为换根dp。
设 $f_u$ 表示 $u$ 所在子树染色的权值， $g_u$ 表示 $u$ 为根时的最大权值，则
钦定 $1$ 为根，则 $g_1 = n + \sum_{v \in \mathtt{son}(u)}f_u$ 。接着考虑换根，设 $y$ 为 $x$ 的一个儿子。
时间复杂度 $\mathcal{O}(n)$
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5+15))
int n,res,pos=1,head[N],f[N],g[N],sz[N];
struct Edge { int u,v,next; } e[N * 2];
void addEdge(int u,int v)
{ e[++pos] = {u,v,head[u]}; head[u] = pos; }
void dfs1(int u,int fa)
{
sz[u] = 1;
for(int i = head[u]; i; i = e[i].next)
{
int v = e[i].v;
if(v == fa) continue;
dfs1(v,u); sz[u] += sz[v];
f[u] += f[v];
}
f[u] += sz[u];
}
void dfs2(int u,int fa)
{
if(u != 1)
{ g[u] = g[fa] + n - sz[u] * 2; up(res, g[u]); }
for(int i = head[u]; i; i = e[i].next)
if(e[i].v != fa) dfs2(e[i].v, u);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n;
for(int i=1,u,v; i<n; i++)
{ cin >> u >> v; addEdge(u,v); addEdge(v,u); }
dfs1(1,0); res = g[1] = f[1]; dfs2(1,0); cout << res << '\n';
return 0;
}参考文献：
