96分玄关求调
查看原帖
96分玄关求调
737325
_klee_楼主2024/7/24 14:51

rt

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (ch<'0'||ch>'9')
	{
		if (ch=='-') f=-1;
		ch=getchar();
	}
	while (ch>='0'&&ch<='9')
	{
		x=x*10+ch-48;
		ch=getchar();
	}
	return x*f;
}
long long n,siz[N],dp[N],f[N],ans;
vector<int> g[N];
void dfs(int x,int fa)
{
	siz[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int to=g[x][i];
		if(to==fa)	continue;
		dfs(to,x);
		siz[x]+=siz[to];
		dp[x]+=dp[to];
	}
	dp[x]+=siz[x];
}
void dfs2(int x,int fa)
{
	for(int i=0;i<g[x].size();++i)
	{
		int to=g[x][i];
		if(to==fa)continue;
		f[to]=n+f[x]-2*siz[to];
		dfs2(to,x);
	}
}
int main( )
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int u,v;
		u=read();
		v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	f[1]=dp[1];
	dfs2(1,0);
	for(int i=1;i<=n;++i)
		ans=max(ans,f[i]);
	printf("%d",ans);
 	return 0;
}
2024/7/24 14:51
加载中...