树的重心

为学树的分治做准备。。。

题目连接：POJ 1655

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 const int maxn=20010;
 6 const int inf=1<<30;
 7 int n,son[maxn],vis[maxn];
 8 int ans,maxson;
 9 struct edge
10 {
11     int v,nex;
12 }e[maxn<<1];
13 int head[maxn];
14 int cnt=0;
15 void add(int u,int v)
16 {
17     e[cnt].v=v;
18     e[cnt].nex=head[u];
19     head[u]=cnt++;
20 }
21 void init()
22 {
23     cnt=0;
24     maxson=inf;
25     memset(head,-1,sizeof(head));
26     memset(vis,0,sizeof(vis));
27 }
28 void dfs(int u)
29 {
30     vis[u]=1;
31     son[u]=0;
32     int temp=0;
33     for(int i=head[u];i!=-1;i=e[i].nex)
34     {
35         int v=e[i].v;
36         if(!vis[v])
37         {
38             dfs(v);
39             son[u]+=son[v]+1;
40             temp=max(temp,son[v]+1);
41         }
42     }
43     temp=max(temp,n-son[u]-1);
44     if(temp<maxson||temp==maxson&&u<ans)
45     {
46         ans=u;
47         maxson=temp;
48     }
49 }
50 int main()
51 {
52     int t;
53     scanf("%d",&t);
54     while(t--)
55     {
56         init();
57         scanf("%d",&n);
58         for(int i=1;i<n;i++)
59         {
60             int u,v;
61             scanf("%d%d",&u,&v);
62             add(u,v);
63             add(v,u);
64         }
65         dfs(1);
66         printf("%d %d
",ans,maxson);
67     }
68 }

View Code

题目连接：POJ 3107

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 using namespace std;
 6 const int maxn=50010;
 7 const int inf=1<<30;
 8 int n,son[maxn],vis[maxn];
 9 int ans[maxn],maxson,num;
10 struct edge
11 {
12     int v,nex;
13 }e[maxn<<1];
14 int head[maxn];
15 int cnt=0;
16 void add(int u,int v)
17 {
18     e[cnt].v=v;
19     e[cnt].nex=head[u];
20     head[u]=cnt++;
21 }
22 void init()
23 {
24     cnt=0;
25     maxson=inf;
26     memset(head,-1,sizeof(head));
27     memset(vis,0,sizeof(vis));
28 }
29 void dfs(int u)
30 {
31     vis[u]=1;
32     son[u]=0;
33     int temp=0;
34     for(int i=head[u];i!=-1;i=e[i].nex)
35     {
36         int v=e[i].v;
37         if(!vis[v])
38         {
39             dfs(v);
40             son[u]+=son[v]+1;
41             temp=max(temp,son[v]+1);
42         }
43     }
44     temp=max(temp,n-son[u]-1);
45     if(temp<maxson)
46     {
47         ans[0]=u;
48         num=1;
49         maxson=temp;
50     }
51     else if(temp==maxson)
52     {
53         ans[num++]=u;
54     }
55 }
56 int main()
57 {
58     while(scanf("%d",&n)!=EOF)
59     {
60         init();
61         for(int i=1;i<n;i++)
62         {
63             int u,v;
64             scanf("%d%d",&u,&v);
65             add(u,v);
66             add(v,u);
67         }
68         dfs(1);
69         sort(ans,ans+num);
70         for(int i=0;i<num-1;i++)
71             printf("%d ",ans[i]);
72         printf("%d
",ans[num-1]);
73     }
74 }

View Code