题意：给定一棵N个点树，询问这个树里面每个点到树上其他点的最大距离。
n<=10000
思路：设f[u,1],f[u,2]为以U为根向下的最长与次长，g[u,1],g[u,2]为从哪个儿子转移来
第一次dfs用V更新U，第二次dfs用U更新V，因为有V向U往上走的情况，这样做就可以处理了
可以发现这些数值中取最大值就是树的直径了
1 var f,g:array[1..21000,1..2]of longint; 2 head,vet,next,len:array[1..21000]of longint; 3 n,x,y,i,tot:longint; 4 5 procedure add(a,b,c:longint); 6 begin 7 inc(tot); 8 next[tot]:=head[a]; 9 vet[tot]:=b; 10 len[tot]:=c; 11 head[a]:=tot; 12 end; 13 14 procedure dfs(u,fa:longint); 15 var e,v,t:longint; 16 begin 17 e:=head[u]; 18 while e<>0 do 19 begin 20 v:=vet[e]; 21 if v<>fa then 22 begin 23 dfs(v,u); 24 t:=f[v,1]+len[e]; 25 if t>f[u,1] then 26 begin 27 f[u,2]:=f[u,1]; g[u,2]:=g[u,1]; 28 f[u,1]:=t; g[u,1]:=v; 29 end 30 else if t>f[u,2] then 31 begin 32 f[u,2]:=t; g[u,2]:=v; 33 end; 34 end; 35 e:=next[e]; 36 end; 37 end; 38 39 procedure dfs2(u,fa:longint); 40 var e,v,t:longint; 41 begin 42 e:=head[u]; 43 while e<>0 do 44 begin 45 v:=vet[e]; 46 if v<>fa then 47 begin 48 t:=f[u,1]+len[e]; 49 if v=g[u,1] then t:=f[u,2]+len[e]; 50 if t>f[v,1] then 51 begin 52 f[v,2]:=f[v,1]; g[v,2]:=g[v,1]; 53 f[v,1]:=t; g[v,1]:=u; 54 end 55 else if t>f[v,2] then 56 begin 57 f[v,2]:=t; g[v,2]:=u; 58 end; 59 dfs2(v,u); 60 end; 61 e:=next[e]; 62 end; 63 end; 64 65 begin 66 assign(input,'2196.in'); reset(input); 67 assign(output,'2196.out'); rewrite(output); 68 while not eof do 69 begin 70 fillchar(head,sizeof(head),0); 71 tot:=0; 72 fillchar(f,sizeof(f),0); 73 fillchar(g,sizeof(g),0); 74 read(n); 75 if n=0 then break; 76 for i:=2 to n do 77 begin 78 read(x,y); 79 add(i,x,y); 80 add(x,i,y); 81 end; 82 dfs(1,-1); 83 dfs2(1,-1); 84 for i:=1 to n do writeln(f[i,1]); 85 end; 86 close(input); 87 close(output); 88 end.