Title translation
给定一棵 (n) 个点的树，初始全是白点。
要做 (n) 步操作，每一次选定一个与一个黑点相隔一条边的白点，将它染成黑点，然后获得该白点被染色前所在的白色联通块大小的权值。第一次操作可以任意选点，求可获得的最大权值。
Solution
如何让这道题秒降绿题呢？
先简化一下题意：
给定一个 (n) 个点的树，请求出一个结点，使得以这个结点为根时，所有结点的深度之和最大，求这个深度。
这不和P3478一样吗！
为何是这样？
我们换个方向思考：
因为每一次是把一个与一个黑点相隔一条边的白点染成黑点，考虑一个节点 (v)，当这棵树的根节点是 (v)、(v) 的父亲、(v) 的父亲的父亲……的时候，(v) 都会给它们所在的联通块大小贡献 (1)。那它最多贡献多少个 (1) 呢？其实就是它自己的深度。
那题目就简化成了刚刚的那样……
Code
#include <bits/stdc++.h> #define int long long using namespace std; const int Maxn=1e6+5; int n;vector<int>e[Maxn]; int Size[Maxn],Dep[Maxn]; int f[Maxn]; void dfs1(int u,int fa){ Size[u]=1;Dep[u]=Dep[fa]+1; for(auto v:e[u]){ if(v==fa)continue; dfs1(v,u); Size[u]+=Size[v]; } } void dfs2(int u,int fa){ for(auto v:e[u]){ if(v==fa)continue; f[v]=f[u]+n-2*Size[v]; dfs2(v,u); } } signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n-1;i++){ int u,v;cin>>u>>v; e[u].push_back(v); e[v].push_back(u); } dfs1(1,0); for(int i=1;i<=n;i++)f[1]+=Dep[i]; dfs2(1,0);int maxn=INT_MIN,id; for(int i=1;i<=n;i++) if(f[i]>maxn)maxn=f[i],id=i; cout<<maxn; return 0; } 
