CF1187E 题解

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;
	}