转自：http://blog.csdn.net/shuangde800
题目大意：
求树上所有点到树上另一点的最远距离；
基本思路：
把无根树转化成有根树分析，
对于上面那棵树，要求距结点2的最长距离，那么，就需要知道以2为顶点的子树（蓝色圈起的部分，我们叫它Tree（2）），距顶点2的最远距离L1
还有知道2的父节点1为根节点的树Tree（1）-Tree(2)部分（即红色圈起部分），距离结点1的最长距离+dist(1,2) = L2，那么最终距离结点2最远的距离就是max{L1，L2}
f[i][0],表示顶点为i的子树的，距顶点i的最长距离
f[i][1],表示Tree(i的父节点)-Tree(i)的最长距离+i跟i的父节点距离
要求所有的f[i][0]很简单，只要先做一次dfs求每个结点到叶子结点的最长距离即可。
然后要求f[i][1], 可以从父节点递推到子节点，
假设节点u有n个子节点，分别是v1,v2...vn
那么
如果vi不是u最长距离经过的节点，f[vi][1] = dist(vi,u)+max(f[u][0], f[u][1])
如果vi是u最长距离经过的节点，那么不能选择f[u][0],因为这保存的就是最长距离，要选择Tree（u）第二大距离secondDist,
可得f[vi][1] = dist(vi, u) + max(secondDist, f[u][1])
代码如下：
#include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<iostream> #include<algorithm> #include<vector> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const double eps = 1e-8; const int maxn = 10000+10; struct Node{ int v,w; }; vector<Node>adj[maxn];bool vis[maxn]; int n,m; ll f[maxn][2]; //求f[u][0] ll dfs1(int u){ vis[u]=true; f[u][0]=0; int sz=adj[u].size(); for(int i=0;i<sz;i++){ int v=adj[u][i].v; int w=adj[u][i].w; if(vis[v]) continue; f[u][0]=max(f[u][0],dfs1(v)+w); } return f[u][0]; }
//求f[u][1] void dfs2(int u,int fa_w){ vis[u]=true; int max1=0,v1,max2=0,v2; int sz=adj[u].size(); for(int i=0;i<sz;++i){ int v=adj[u][i].v; int w=adj[u][i].w; if(vis[v]) continue; int tmp=f[v][0]+w; if(tmp>max1){ max2=max1;v2=v1; max1=tmp;v1=v; }else if(tmp==max1||tmp>max2){ max2=tmp; v2=v; } } if(u!=1){ int tmp=f[u][1]; int v=-1; if(tmp>max1){ max2=max1;v2=v1; max1=tmp;v1=v; }else if(tmp==max1||tmp>max2){ max2=tmp; v2=v; } } for(int i=0;i<sz;i++){ int v=adj[u][i].v; int w=adj[u][i].w; if(vis[v]){ continue; } if(v==v1){ f[v][1]=max2+w; }else{ f[v][1]=max1+w; }//如果v==v1，说明v1在u的最长距离上，那么v的最长距离就不能用max1，只能用max2； dfs2(v,w); } } int main(){ while(~scanf("%d",&n)&&n){ for(int i=1;i<=n;i++){ adj[i].clear(); } for(int u=2;u<=n;u++){ int v,w; scanf("%d%d",&v,&w); adj[u].push_back((Node){v,w}); adj[v].push_back((Node){u,w}); } memset(f,0,sizeof(f)); memset(vis,0,sizeof(vis)); dfs1(1); memset(vis,0,sizeof(vis)); dfs2(1,0); for(int i=1;i<=n;i++){ printf("%lld ",max(f[i][0],f[i][1])); } } return 0; }