题目链接：hdu 2196 Computer
题意：
给你一棵n个节点,n-1条边的树，每条边有一个长度，求没，每个点到最远距离的点的长度。
题解：
紫书上也有讲：
求一棵树最长的边的方法：随便找个点，dfs一遍求到长度最长的点s。
然后以s点为根dfs一遍，同样找到长度最长的点t。
然后在以t点为根，dfs一遍,求到所有点到t点的距离，
对于每个点到最远距离的点的长度就是max(dis_s[i],dis_t[i])。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 const int N=1e4+7; 5 6 int g[N],v[N*2],nxt[2*N],w[2*N],ed,n,s,t,dt[N],ds[N]; 7 8 void adg(int x,int y,int z){v[++ed]=y,w[ed]=z,nxt[ed]=g[x],g[x]=ed;} 9 10 void dfs(int x,int fa,int dep,int *dis) 11 { 12 dis[x]=dep; 13 for(int i=g[x];i;i=nxt[i]) 14 if(v[i]!=fa)dfs(v[i],x,dep+w[i],dis); 15 } 16 17 int main(){ 18 while(~scanf("%d",&n)) 19 { 20 F(i,1,n)g[i]=0;ed=0; 21 F(i,2,n) 22 { 23 int a,b; 24 scanf("%d%d",&a,&b); 25 adg(i,a,b),adg(a,i,b); 26 } 27 dfs(1,0,0,ds); 28 int mx=0; 29 F(i,1,n)if(ds[i]>mx)s=i,mx=ds[i]; 30 dfs(s,0,0,ds); 31 mx=0; 32 F(i,1,n)if(ds[i]>mx)t=i,mx=ds[i]; 33 dfs(t,0,0,dt); 34 F(i,1,n)printf("%d ",max(ds[i],dt[i])); 35 } 36 return 0; 37 }