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