poj 1655 树的重心

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <stack>
 7 #include <queue>
 8 #include <cmath>
 9 #include <map>
10 #define ll  __int64
11 #define dazhi 2147483647
12 #define bug() printf("!!!!!!!")
13 #define M 200005
14 using namespace  std;
15 struct node
16 {
17     int from;
18     int to;
19 } N[4*M];
20 int n;
21 int pre[M];
22 int nedge=0;
23 int son[M];
24 int vis[M];
25 int l;
26 int r;
27 int ans;
28 int re;
29 int t;
30 void add(int f,int t)
31 {
32     nedge++;
33     N[nedge].to=t;
34     N[nedge].from=pre[f];
35     pre[f]=nedge;
36 }
37 int getnode(int root)
38 {
39     vis[root]=1;
40     son[root]=0;
41     int temp=0;
42     for(int i=pre[root];i;i=N[i].from)
43     {
44         int x=N[i].to;
45         if(vis[x]==0)
46         {
47             getnode(x);
48             son[root]+=son[x]+1;
49             temp=max(temp,son[x]+1);
50         }
51     }
52     temp=max(temp,n-son[root]-1);
53     if(temp<ans||(temp==ans&&root<re))
54     {
55         ans=temp;
56         re=root;
57     }
58 }
59 int main()
60 {
61     scanf("%d",&t);
62     for(int j=1; j<=t; j++)
63     {
64         memset(pre,0,sizeof(pre));
65         memset(N,0,sizeof(N));
66         memset(vis,0,sizeof(vis));
67         nedge=0;
68         re=M;
69         ans=M;
70         scanf("%d",&n);
71         for(int i=1; i<=n-1; i++)
72         {
73             scanf("%d %d",&l,&r);
74             add(l,r);
75             add(r,l);
76         }
77         getnode(1);
78         printf("%d %d\n",re,ans);
79     }
80     return 0;
81 }