poj 3107 Godfather

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树的重心

题意:给出一个无根树,确定树的重心,如果有多个,按升序输出。按照树的重心的性质,只有有1个或2个重心,所以直接用root,__root来记录

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 50010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,tot,head[N];
struct edge{
int v,next;
}e[2*N];
int Max[N],cnt[N],Min,root,__root;

void dfs(int u,int fa){
Max[u] = 0; cnt[u] = 1;
for(int k = head[u] ; k != -1; k = e[k].next){
int v = e[k].v;
if(v == fa) continue;
dfs(v,u);
cnt[u] += cnt[v];
Max[u] = max(Max[u] , cnt[v]);
}
Max[u] = max(Max[u] , n - cnt[u]);
if(Max[u] < Min){
Min = Max[u];
root = u; __root = -1;
}
else if(Max[u] == Min){
Min = Max[u];
__root = u;
if(root > __root)
swap(root,__root);
}
}

int main(){
while(scanf("%d",&n)!=EOF){
cl(head,-1); tot = 0;
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
e[tot].v = v; e[tot].next = head[u]; head[u] = tot++;
e[tot].v = u; e[tot].next = head[v]; head[v] = tot++;
}
Min = 100000000;
root = __root = -1;
dfs(1,-1);
printf("%d",root);
if(__root != -1) printf(" %d",__root);
puts("");
}
return 0;
}