记录编号	202310	评测结果	AAAAAAAA
题目名称	[石门中学 2009]切割树	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2015-10-31 21:34:25	内存使用	2.22 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
int n,tot=0,h[maxn];
struct edge{
	int to,next;
}G[maxn];
int opt[maxn],ans[maxn],Ans=0;

void add(int x,int y){
	++tot; G[tot].to=y;
	G[tot].next=h[x]; h[x]=tot;
}

void tree_dp(int x,int fa){
	if (opt[x]) return;
	for (int i=h[x];i;i=G[i].next){
		int v=G[i].to;
		if (v==fa) continue;
		tree_dp(v,x);
		opt[x]+=opt[v];
	} opt[x]++;
	int k1=n-opt[x];
	if (k1<=n/2){
		bool flag=1;
	    for (int i=h[x];i;i=G[i].next)
		    if (G[i].to!=fa)
				if (opt[G[i].to]>n/2){flag=0;break;}
		if (flag) ans[++Ans]=x;
	}
}

int main(){
	freopen("treecut.in","r",stdin);
	freopen("treecut.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<n;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	tree_dp(1,-1);
	sort(ans+1,ans+Ans+1);
	for (int i=1;i<=Ans;++i)
		printf("%d ",ans[i]);
	return 0;
}