90pts求助
查看原帖
90pts求助
569284
zhoukeyi楼主2022/12/17 13:53

不知道错那了

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int n,m,head[1000005],num,ans,f[1000005],o[1000005],dep[1000005];
struct edge{
    int to,pre; 
}edge[1000005*2];
void add(int from,int to){
    edge[num].to=to;
    edge[num].pre=head[from];
    head[from]=num++;
}
void dfs(int u,int fa){
	o[u]=1;
	dep[u]=dep[fa]+1;
	for(int i=head[u];i;i=edge[i].pre){
        int v=edge[i].to;
    	if(v!=fa){
			dfs(v,u);
    		o[u]+=o[v];
		}
    }
}
void mbwhq(int u,int fa){
    for(int i=head[u];i;i=edge[i].pre){
        int v=edge[i].to;
    	if(v!=fa){
    		f[v]=f[u]-o[v]*2+n;
    		mbwhq(v,u);
		}
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
    	int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    dfs(1,1);
    for(int i=1;i<=n;i++){
    	f[1]+=dep[i]; 
	}
	mbwhq(1,1);
	int caixukun=-1,ngm;
	for(int i=1;i<=n;i++){
		if(f[i]>caixukun){
			caixukun=f[i];
			ngm=i;
		}
	}
	cout<<ngm; 
    return 0;
}
2022/12/17 13:53
加载中...