treecut
题目描述：有一个N个节点的无根树，各节点编号为1..N，现在要求你删除其中的一个点，使分割开的连通块中节点个数都不超过原来的一半多。
数据范围（1 <= N <= 10,000）
输入文件 treecut.in
第一行：一个整数N。
后面有N-1行：每行两个整数 X 和 Y，表示一个边连接的两个节点号。
输出文件 treecut.out
输出所有可能选择的点。如果有多个节点，按编号从小到大输出，每个一行。如果找不到这样的点，输出一行："NONE".
样例
输入
10
1 2
2 3
3 4
4 5
6 7
7 8
8 9
9 10
3 8
样例说明：
删除3号或8号
节点，则分枝
最多有5个节点
输出
3
8

const
inf='treecut.in';
ouf='treecut.out';
maxn=10010;
type
node=^node2;
node2=record
data:longint;
next:node;
end;
var
n:longint;
son:array[0..maxn] of node;
f:array[0..maxn] of longint;
v:array[0..maxn] of boolean;
procedure add(x,y:longint);
var
p:node;
begin
new(p);
p^.data:=y; p^.next:=son[x];
son[x]:=p;
end;
procedure init;
var
i,x,y:longint;
begin
readln(n);
for i:=1 to n do son[i]:=nil;
for i:=1 to n-1 do
begin
readln(x,y);
add(x,y);
add(y,x);
end;
end;
procedure treedp(x:longint);
var
p:node;
begin
v[x]:=true;
p:=son[x];
if p=nil then
begin
f[x]:=1;
exit;
end;
while p<>nil do
begin
if not v[p^.data] then
begin
treedp(p^.data);
f[x]:=f[x]+f[p^.data];
end;
p:=p^.next;
end;
inc(f[x]);
end;
procedure main;
var
i,now:longint;
p:node;
flag:boolean;
begin
flag:=false;
for i:=1 to n do
begin
p:=son[i];
now:=n-f[i];
while p<>nil do
begin
if (f[p^.data]<f[i]) and (now<f[p^.data]) then now:=f[p^.data];
p:=p^.next;
end;
if now<=n div 2 then begin writeln(i); flag:=true; end;
end;
if not flag then writeln('NONE');
end;
begin
assign(input,inf); reset(input);
assign(output,ouf);rewrite(output);
init;
treedp(1);
main;
close(input); close(output);
end.