Godfather

Godfather

‎去年，芝加哥到处都是黑帮大战和奇怪的谋杀案。警察局长对所有这些罪行感到非常厌倦，并决定逮捕黑手党领导人。‎

‎不幸的是，芝加哥黑手党的结构相当复杂。已知有‎‎n‎‎个人与黑手党有关。警方已经追踪了他们的活动一段时间，并知道他们中的一些人正在相互交流。根据收集到的数据，警察局长认为黑手党的等级制度可以表示为一棵树。黑手党的头目教父是树的根，如果某人由树中的节点表示，则其直接下属由该节点的子级表示。为了阴谋的目的，歹徒只与他们的直接下属和他们的直接主人沟通。‎

‎不幸的是，虽然警察知道歹徒的通讯，但他们不知道谁是任何一对通讯人员中的大师。因此，他们只有一棵无向的沟通树，不知道教父是谁。‎

‎基于教父希望对黑手党拥有最大可能控制权的想法，警察局长建议教父是这样的人，从通信树中删除后，剩余的最大连接组件的大小尽可能小。帮助警察找到所有潜在的教父，他们会逮捕他们。‎

Input

‎输入文件的第一行包含‎‎n‎‎ - 涉嫌属于黑手党的人数（2≤‎‎n‎‎≤50 000）。让它们从1到‎‎n‎‎编号。‎

‎以下 ‎‎n‎‎ − 1 行各包含两个整数。对‎‎a‎‎i‎‎，‎‎b‎‎i‎‎表示歹徒‎‎a‎‎i‎‎与歹徒‎‎b‎‎i‎‎通信。可以保证歹徒的通信形成一棵树。‎

Output

‎打印所有被怀疑是教父的人的号码。这些数字必须按递增的顺序打印，并用空格分隔。‎

Sample

6
1 2
2 3
2 5
3 4
3 6

2 3

 
#include 
#include 
using namespace std;
inline void add(int x, int y); 
inline void dfs(int x, int fa);
int n;
struct edge
{
	int nxt;
	int  to;
}ed[100010];
int head[50010], cnt;
inline void add(int x, int y)
{
ed[++cnt].nxt=head[x];
ed[cnt].to= y;
head[x]=cnt;
}
int siz[50010];
int f[50010];
int fat[50010];
int mx=1e9;
 
inline void dfs(int x, int fa)
{
	siz[x] = 1;
	for (int i = head[x]; i; i = ed[i].nxt)
	{
		int to = ed[i].to;
		if (fa == to) continue;
		fat[to] = x;
		dfs(to, x);
		siz[x] += siz[to];
	}
}
 
int main()
{
	scanf("%d", &n);
	for (int i = 1; i < n; i++)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		add(x, y);
	    add(y, x);
	}
	dfs(1, 0);
	for ( int x = 1; x <= n; x ++)
	{
		int sum=0;
		for (int i = head[x]; i; i = ed[i].nxt)
		{
			int to = ed[i].to;
			if (to == fat[x]) sum = max(sum, siz[1] - siz[x]);
			else sum = max(sum, siz[to]);
		}
		f[x] = sum;
		mx = min(mx, f[x]);
	}
	for ( int i = 1; i <= n; i ++)
	{
		if (f[i] == mx) printf("%d ", i);
	}
	return 0;
}