[codevs 3639] 树的中心---树形DP(树的重心)

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define open(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define close fclose(stdin); fclose(stdout); 
using namespace std;

struct node //树的节点
{
	vector<int>ch;
	int d; // size
	int ma; //子树孩子的最大值
};

struct Edge //邻接表(链式向前星)
{
	int to;
	int next;
};

int ank; // 找K值
vector<int>ans; //记录节点
int n;
int cnt;
int head[16005];
Edge edge[32005];
node tree[16005];
bool vis[16005];

inline int read()
{
	int k=1;
	int sum=0;
	char c=getchar();
	for(;'0'>c || c>'9' ;c=getchar())
		if(c=='-') k=-1;
	for(;'0'<=c && c<='9';c=getchar())
		sum=sum*10+c-'0';
	return sum*k;
}

inline void write(int x)
{
	if(x<0) { putchar('-'); x*=-1; }
	if(x>9) write(x/10);
	putchar(x%10+'0');
}

inline void add(int x,int y) 
{
	++cnt;
	edge[cnt].to=y;
	edge[cnt].next=head[x];
	head[x]=cnt;
}

inline int max(int x,int y)
{
	return x>y?x:y;
}

inline void build(int p)
{
	for(int i=head[p];i;i=edge[i].next) // 建树
	if(!vis[edge[i].to])
	{
		int y=edge[i].to;
		vis[y]=1; //初始化
		tree[y].d=1;
		tree[p].ch.push_back(y);
		build(y);
		tree[p].d+=tree[y].d; //更新d/ma
		tree[p].ma=max(tree[p].ma,tree[y].d); 
	}
	tree[p].ma=max(tree[p].ma,n-tree[p].d); // 更新答案
	if(ank==-1 || tree[p].ma<ank)
	{
		ank=tree[p].ma;
		ans.clear();
		ans.push_back(p);
	}else
	if(tree[p].ma==ank)
		ans.push_back(p);
}

inline bool cmp(int x,int y)
{
	return x<y;
}

int main()
{
	open("tree");

    n=read();
	for(int i=1;i<n;++i)
	{
		int x=read(),y=read();
		add(x,y);
		add(y,x);
	}
	vis[1]=1; //初始化
	tree[1].d=1;
	ank=-1;
	build(1);

	sort(ans.begin(),ans.end(),cmp); //答案要求
	int s=ans.size();
	write(ank);putchar(' ');write(s);putchar('n');
    for(int i=0;i<s;++i)
	{
		write(ans[i]);
		putchar(' ');
	}
	
    close;
	return 0;
}