学步园

有些问题需要说明本题目求的是在树上求最远点对的扩展题目；
求最远点对可分为两种做法； 第一，任意选择一点直接dfs其到其子节点的最远距离，然后选出两个最长的u，v 答案为 u+v+2
这样做的原因很简单，因为最远路径一定在求解的经过树中某点折为两段或者是未被弯折；
第二种做法为，先取一点直接dfs求它的最远点u，则u一定是最远点对中的一个（可尝试画图看一看），换句话说所有节点的最远点都是
最远点对中的一个；然后从该点再dfs一次即可；

结合上面两种方法；可解决此题；先找到一个最远点对中的点u；然后从u dfs求每个点到叶节点的最远距离，
第二步，还是从u开始，dfs  每次当下要处理的节点v都是最远路线上一点，找到他在最远线上的孩子，其他孩子构成的子树
直接另起 遍历一遍，对子树中每个节点p 以max（d[v],maxlen - d[v]）+ dis（p -> v）为其最远长度；然后递归该子树；
#include <map>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxn = 10100;
vector<int> G[maxn];
int U,d[maxn];
struct node{
   int x,y;
   node(int x=0,int y=0):x(x),y(y){}
   bool operator < (const node& rhs) const{
      return x < rhs.x || x == rhs.x&&y<rhs.y;
   }
   bool operator == (const node& rhs) const{
     return x == rhs.x&&y==rhs.y;
   }
};
map<node,int> c;
void find(int u,int f){
    d[u] = 0;
    for(int i=0;i<G[u].size();i++){
       if(G[u][i]==f) continue;
       find(G[u][i],u);
       d[u]=max(d[u],d[G[u][i]]+c[node(u,G[u][i])]);
    }
}
void get(int u,int f){
    if(G[u].size()==1&&G[u][0]==f){
         U=u; return ;
    }
    for(int i=0;i<G[u].size();i++){
       if(G[u][i]==f) continue;
       int v = G[u][i];
       if(d[u]==d[v]+c[node(u,G[u][i])]){
            get(v,u); break;
       }
    }
}
int Find(){
    find(1,-1);
    get(1,-1);
}
int dis[maxn],LEN;
void dfs2(int u,int floor,int add,int fa){
     dis[u] = add + floor;
     for(int i=0;i<G[u].size();i++){
           if(G[u][i]==fa) continue;
           dfs2(G[u][i],floor+c[node(u,G[u][i])],add,u);
     }
}
void dfs(int u,int fa){
     int maxv=-1;
     for(int i=0;i<G[u].size();i++){
           if(G[u][i]==fa) continue;
           int v =G[u][i];
           if(d[u]==d[v]+c[node(u,G[u][i])]) {
               dis[v] = max(d[v],LEN - d[v]);
               maxv = v; break;
           }
     }
     for(int i=0;i<G[u].size();i++){
           if(G[u][i]==fa) continue;
           if(G[u][i]==maxv) continue;
           dfs2(G[u][i],c[node(u,G[u][i])],max(d[u],LEN-d[u]),u);
     }
     if(maxv!=-1) dfs(maxv,u);
}
int main()
{
   int n;
   while(scanf("%d",&n)==1){
        for(int i=1;i<=n;i++) G[i].clear();
        c.clear();
        for(int i=2;i<=n;i++){
         int x,y;
         scanf("%d %d",&x,&y);
         G[i].push_back(x);
         G[x].push_back(i);
         c[node(i,x)]=c[node(x,i)]=y;
        }
        Find();
        find(U,-1);
        dis[U]= LEN = d[U];
        dfs(U,-1);
        for(int i=1;i<=n;i++){
              cout<<dis[i]<<endl;
        }
   }
   return 0;
}