CF1187E Question

Title translation

Given a tree\(n\) A tree of points.Initially all white dots。

do\(n\) step operation, each time one of the selectedA white dot one edge away from a black dotDye it.black spotThen get that white dotstainedlocatedWhite Connections Block SizeThe weights of theYou can select any point for the first operationThe amount of availableMaximum weights。

Solution

How do you get this question down to green in seconds?

Let's simplify the question first:

Given a\(n\) A tree of points is requested to find thea nodemakesWith this node as the rootWhen all nodes ofMaximum sum of depthsI'm begging for this.(of a speech etc) profundity。

It's not the same asP3478Same?

Why is that?

Let's think in another direction:

Because every time it'sColor a white dot one edge away from a black dot black., consider a node\(v\)When the tree'sroot nodebe\(v\)、\(v\) The father,\(v\) The father of the father of the father of the father of the father of the father of the father of the father of the father.……when，\(v\) It's all for them.The size of the connectivity block in which it is locateddedicate\(1\). Then it's at mostHow many contributions \(1\) What about it? It's actually its own(of a speech etc) profundity。

Then the title simplifies to what it just was ......

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);
		(0); (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;
	}