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 u_i, v_i n $ , $ u_i 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\) 为根时的最大权值，则 \[ f_u = \mathtt{size}(u) + \sum_{v \in \mathtt{son}(u)}f_v \] 钦定 \(1\) 为根，则 \(g_1 = n + \sum_{v \in \mathtt{son}(u)}f_u\) 。接着考虑换根，设 \(y\) 为 \(x\) 的一个儿子。 \[ \begin{aligned} g_y &= n + n - \mathtt{size}(y) + \sum_{v\in \mathtt{son}(x) \land v \ne y}f_v + \sum_{v \in \mathtt{son}(y)}f_v \\[6pt] &= 2n - \mathtt{size}(y) + \sum_{v\in \mathtt{son}(x) \land v \ne y}f_v + f_y - \mathtt{size}(y) \\[6pt] &= 2n - \mathtt{size}(y) + \sum_{v \in \mathtt{son}(x)}f_v - \mathtt{size}(y) \\[6pt] &= g_x + n - 2\times \mathtt{size}(y) \end{aligned} \] 时间复杂度 \(\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;
}参考文献：
