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 57 58 59 60 61 62 63 64 65
| #include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; typedef long long LL; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=1000005; int n,Size[maxn],Ans2=1; LL Ans=0; vector<int>edges[maxn]; void AddEdge(int x,int y) { edges[x].push_back(y); } void Dfs(int Now,int father,int depth) { Size[Now]=1; Ans+=depth; for(int& Next:edges[Now]) { if(Next==father)continue; Dfs(Next,Now,depth+1); Size[Now]+=Size[Next]; } } void TreeDp(int Now,int father,LL ans) { if(Now!=1) { ans=ans+n-2*Size[Now]; if(ans>Ans) { Ans=ans; Ans2=Now; } else if(ans==Ans&&Now<Ans2)Ans2=Now; } for(int& Next:edges[Now]) { if(Next==father)continue; TreeDp(Next,Now,ans); } } int main() { n=Get_Int(); for(int i=1; i<n; i++) { int x=Get_Int(),y=Get_Int(); AddEdge(x,y); AddEdge(y,x); } Dfs(1,0,1); TreeDp(1,0,Ans); printf("%d\n",Ans2); return 0; }
|