有大佬帮忙看一下吗 re了
查看原帖
有大佬帮忙看一下吗 re了
1103294
yuanshuu楼主2024/8/31 19:56
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
//链式前向星存树
struct node{
	int to;
	int nxt;
} edge[2000004];
int head[1000005];
inline void add(int i,int u,int v){
	edge[i].to=v;
	edge[i].nxt=head[u];
	head[u]=i;
	return ;
}

int size[1000004];//以u为根的树的大小
int sum[1000004];//以u为根,所有子节点到该节点的距离和
void dfs1(int u,int fa){
	size[u]=1;
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v!=fa){
			dfs1(v,u);
			sum[u]+=sum[v]+size[v];
			size[u]+=size[v];
		}
	}
	return ;
}
int dp[1000004],maxx,ans;
void dfs2(int u,int fa){
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v!=fa){
			dp[v]=dp[u]-size[v]+n-size[v];
			dfs2(v,u);
		}
	}
	if(dp[u]>maxx){
		ans=u;
		maxx=dp[u];
	}
	return ;
}

signed main (){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(1<<i,x,y);
		add((1<<i)-1,y,x);
	}
	dfs1(1,0);
//	for(int i=1;i<=n;i++){
//		cout<<i<<" "<<size[i]<<" "<<sum[i]<<endl;
//	}
	dp[1]=sum[1];
	dfs2(1,0);
	cout<<ans<<endl;
	return 0;
}
2024/8/31 19:56
加载中...