1301. treecut (Standard IO)

Description

有一个N个节点的无根树，各节点编号为1..N，现在要求你删除其中的一个点，使分割开的连通块中节点个数都不超过原来的一半多。

Input

第一行：一个整数N (1 <= N <= 10,000)。 　　后面有N-1行：每行两个整数 X 和 Y，表示一个边连接的两个节点号。

Output

输出所有可能选择的点。如果有多个节点，按编号从小到大输出，每个一行。 如果找不到这样的点，输出一行："NONE".

Sample Input

10 
1 2 
2 3 
3 4 
4 5 
6 7 
7 8 
8 9 
9 10 
3 8

Sample Output

3 8

思路

因为是一棵无根树，所以随便找一个点当根节点，做一次dfs，s[i]统计以i为根节点时共有多少个节点，最后如果一个点所有儿子的s都不超过n的一半且总结点减去此节点的s值也不超过n的一半，那么这个点就可以删除。

vars:array[1..10000] of longint;f:array[1..10000,1..10000] of boolean;a,d:array[1..10000] of boolean;n:longint;
procedure xxoo(x:longint);
vari:longint;c:boolean;
begina[x]:=false;c:=true;for i:=1 to n dobeginif (f[i,x])and(a[i]) thenbeginxxoo(i);s[x]:=s[x]+s[i];if s[i]>n div 2 thenc:=false;end;end;if n-s[x]>n div 2 thenc:=false;if c then d[x]:=true;
end;
vari,x,y:longint;c:boolean;
beginreadln(n);for i:=1 to n-1 dobeginreadln(x,y);f[x,y]:=true;f[y,x]:=true;end;fillchar(a,sizeof(a),true);for i:=1 to n doinc(s[i]);xxoo(1);for i:=1 to n doif d[i] then writeln(i);
end.