| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
1A了.type node=^ts; ts=record data:longint; next:node; end;
var tmpson,son:array[0..20000] of node;
fmax,fsum,q:array[0..20000] of longint;
getin:array[0..20000] of boolean;
t,tt,i,k,j,n,u,v,ans,num:longint;
p:node;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;
procedure dfs(num:longint);
var p:node; j:longint;
begin
p:=son[num];
while p<>nil do
with p^ do
begin
dfs(data);
if fsum[data]>fmax[num] then fmax[num]:=fsum[data];
inc(fsum[num],fsum[data]);
p:=next;
end;
inc(fsum[num]);
end;
procedure add1(a,b:longint);
var p:node;
begin
p:=son[b];
if p=nil then begin new(son[b]); son[b]^.data:=a; son[b]^.next:=nil; exit; end;
while p^.next<>nil do p:=p^.next;
new(p^.next); p:=p^.next; p^.data:=a; p^.next:=nil;
end;
procedure bfs;
var i,k,j,l,r,now:longint; p:node;
begin
fillchar(getin,sizeof(getin),0);
l:=0; r:=1; getin[1]:=true; q[1]:=1;
repeat
inc(l); now:=q[l];
p:=tmpson[now];
while p<>nil do
with p^ do
begin
if not getin[data] then begin add1(data,now); inc(r); q[r]:=data; end;
getin[data]:=true; p:=next;
end;
until l>=r;
end;
procedure add(a,b:longint);
var p:node;
begin
p:=tmpson[b];
if p=nil then begin new(tmpson[b]); tmpson[b]^.data:=a; tmpson[b]^.next:=nil; end else
begin
while (p^.next<>nil) do p:=p^.next;
new(p^.next); p:=p^.next; p^.data:=a; p^.next:=nil;
end;
end;
begin
readln(T);
for tt:=1 to T do
begin
readln(n);
for i:=1 to n do
begin
if tmpson[i]<>nil then begin dispose(tmpson[i]); tmpson[i]:=nil; end;
if son[i]<>nil then begin dispose(son[i]); son[i]:=nil; end;
end;
for i:=1 to n-1 do
begin
readln(u,v);
add(v,u); add(u,v);
end;
fillchar(fsum,sizeof(fsum),0);
fillchar(fmax,sizeof(fmax),0);
bfs;
dfs(1); num:=0; ans:=maxlongint;
for i:=1 to n do
if max(fsum[1]-fsum[i],fmax[i])<ans then begin ans:=max(fsum[1]-fsum[i],fmax[i]); num:=i; end;
writeln(num,' ',ans);
end;
end.
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator