1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
|
#include<string.h> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; void (int&res){ res=0;char c; while(c=getchar(),c<48); do res=res*10+(c&15); while(c=getchar(),c>47); } const int N=1000005; int n,tot_edge,head[N]; struct Edge{ int to,nxt; }edge[N<<1]; void add_edge(int a,int b){ edge[tot_edge]=(Edge){b,head[a]}; head[a]=tot_edge++; } int cnt[N]; ll sum[N]; void dfs(int p,int f){ cnt[p]=1; for(int i=head[p];~i;i=edge[i].nxt){ int to=edge[i].to; if(to==f)continue; dfs(to,p); cnt[p]+=cnt[to]; } } void solve(int p,int f){ for(int i=head[p];~i;i=edge[i].nxt){ int to=edge[i].to; if(to==f)continue; sum[to]=sum[p]+n-cnt[to]*2; solve(to,p); } } int main(){ Rd(n); memset(head,-1,sizeof(head)); for(int i=1,a,b;i<n;i++){ Rd(a),Rd(b); add_edge(a,b); add_edge(b,a); } dfs(1,0); solve(1,0); ll mx=-1;int ans_id; for(int i=1;i<=n;i++) if(sum[i]>mx)mx=sum[i],ans_id=i; printf("%dn",ans_id); return 0; }
|
近期评论