codevs3639

题目描述 Description

给出一棵树，求出树的中心。

为了定义树的中心，首先给每个结点进行标号。对于一个结点K，如果把K从树中删除（连同与它相连的边一起），剩下的被分成了很多块，每一块显然又是一棵树（即剩下的部分构成了一个森林）。则给结点K所标的号就是森林中结点个数最多的树所拥有的结点数。如果结点K的标号不大于其他任何一个结点的标号，则结点K被称为是树的中心。

输入描述 Input Description

输入：

输入的第一行包含一个整数N（1≤N≤16 000），表示树中的结点数。接下来N-1行，每个两个整数a,b，由一个空格分隔，表示a与b之间有一条边。

输出描述 Output Description

输出：

输出两行，第一行两个整数v,T，v表示树的中心结点的标号，T表示树有多少个中心。第二行包含T个数，为所有树的中心的编号，按升序排列。

样例输入 Sample Input

样例输入：

1 2

2 3

2 4

1 5

5 6

6 7

样例输出 Sample Output

样例输出：

3 1

数据范围及提示 Data Size & Hint

数据范围: 20% N<=100 100% N<=16 000

______________________________________________________________________________________________________

树形动归

深搜，得到每个点为根的子树的大小，n-每个子树大小得到，这其中较大值为大小，值最小的点就是重心。

_______________________________________________________________________________________________________

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=16010;
 4 int n;
 5 struct edge
 6 {
 7     int u,v,next;
 8 }e[maxn<<1];
 9 int head[maxn],js;
10 int size[maxn],ss[maxn];
11 void addage(int u,int v)
12 {
13     e[++js].u=u;e[js].v=v;
14     e[js].next=head[u];head[u]=js;
15 }
16 void dfs(int u,int fa)
17 {
18     size[u]=1;
19     for(int i=head[u];i;i=e[i].next)
20     {
21         int v=e[i].v;
22         if(v!=fa)
23         {
24             dfs(v,u);
25             if(size[v]>ss[u])ss[u]=size[v];
26             size[u]+=size[v];
27         }
28     }
29     if(ss[u]<n-size[u])ss[u]=n-size[u];
30 }
31 int main()
32 {
33     scanf("%d",&n);
34     for(int u,v,i=1;i<n;++i)
35     {
36         scanf("%d%d",&u,&v);
37         addage(u,v);
38         addage(v,u);
39     }
40     dfs(1,0);
41     int sz=n,nn=0;
42     for(int i=1;i<=n;++i)
43     {
44         if(ss[i]<sz)
45         {
46             sz=ss[i];
47             nn=1;
48         }
49         else if(ss[i]==sz)nn++;
50     }
51     printf("%d %d
",sz,nn);
52     for(int i =1;i<=n;++i)
53         if(ss[i]==sz)printf("%d ",i);
54     return 0;
55 }

View Code