1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<vector> 5 #include<queue> 6 using namespace std; 7  8 inline int read(){ 9     char ch;10     int re=0;11     bool flag=0;12     while((ch=getchar())!=‘-‘&&(ch<‘0‘||ch>‘9‘));13     ch==‘-‘?flag=1:re=ch-‘0‘;14     while((ch=getchar())>=‘0‘&&ch<=‘9‘)  re=re*10+ch-‘0‘;15     return flag?-re:re;16 }17 18 struct edge{19     int to,w;20     edge(int to=0,int w=0):21         to(to),w(w){}22 };23 24 const int maxn=10001,maxm=50001;25 int n;26 vector<edge> G[maxn];27 int son[maxn],F[maxn],sum;28 bool vis[maxn];29 int root;30 31 inline void add_edge(int from,int to,int w){32     G[from].push_back(edge(to,w));33     G[to].push_back(edge(from,w));34 }35 36 void init(){37     n=read();38     for(int i=0;i<n-1;i++){39         int from=read(),to=read(),w=read();40         add_edge(from,to,w);41     }42 }43 44 void getroot(int x,int fa){45     son[x]=1;46     F[x]=0;47     int dd=G[x].size();48     for(int i=0;i<dd;i++){49         edge &e=G[x][i];50         if(e.to!=fa&&!vis[e.to]){51             getroot(e.to,x);52             son[x]+=son[e.to];53             F[x]=max(F[x],son[e.to]);54         }55     }56     F[x]=max(F[x],sum-son[x]);57     if(F[x]<F[root])  root=x;58 }59 60 void solve(int x){61     vis[x]=1;62     int dd=G[x].size();63     for(int i=0;i<dd;i++){64         edge &e=G[x][i];65         if(!vis[e.to]){66             root=0;67             sum=e.to;68             getroot(x,0);69             solve(e.to);70         }71     }72 }73 74 int main(){75     //freopen("temp.in","r",stdin);76     init();77     sum=F[root=0]=n;78     memset(vis,0,sizeof vis);79     getroot(1,0);80     printf("%d\n",root);81     memset(vis,0,sizeof vis);82     solve(root);83     return 0;84 }