题意:很简单，就是给你一棵树，每条边都有一定的权值，然后让你找到每个点所能走到的最远距离
链接:点我
那么我们可以这样高效的来处理
先以 1 作为根节点进行一次 dfs 遍历，遍历的时候把以 第 i 为根节点往子树方向可以走到的最远距离和次远距离给求出来，且这两个距离是不在同一个分支中的
然后我们进行第二次的从根节点开始dfs遍历，这时候我们要判断的是对于一个节点 i ，除了子树方向上可能有最远距离外，我通过父节点方向是否可以有更加远的距离
，而对于这个操作，我们只要访问父节点所能到达的最远距离，然后接上一段就行了，但是这里会产生一个问题——就是父节点的最远距离可能是会经过当前这个节点
的，因此我们要进行判断当前节点是否在父节点的最远距离的分支上
如果在的话，那么我们要换一个分支，且要是最远的，这个其实就是第一次dfs中求出的与最远路径不在同一分支上的次远路径，我们接上这段进行转移
如果不在的话，那么我们直接接上父节点的最远路径进行转移就行了
Sample Input
5
1 1 //2到1的距离为1
2 1 //3到2的距离为1
3 1
1 1
Sample Output
3 2 3 4 4
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 #include<map> 8 using namespace std; 9 #define MOD 1000000007 10 const int INF=0x3f3f3f3f; 11 const double eps=1e-5; 12 typedef long long ll; 13 #define cl(a) memset(a,0,sizeof(a)) 14 #define ts printf("***** "); 15 const int MAXN=10015; 16 int n,m,tt; 17 int tot,head[MAXN]; 18 int maxn[MAXN];//该节点往下到叶子的最大距离 19 int smaxn[MAXN];//次大距离 20 int maxid[MAXN];//最大距离对应的序号 21 int smaxid[MAXN];//次大的序号 22 struct Edge 23 { 24 int to,next,w; 25 }edge[MAXN*2]; 26 void addedge(int u,int v,int w) 27 { 28 edge[tot].to=v; 29 edge[tot].w=w; 30 edge[tot].next=head[u]; 31 head[u]=tot++; 32 } 33 void init() 34 { 35 memset(head,-1,sizeof(head)); 36 cl(maxn); 37 cl(smaxn); 38 tot=0; 39 } 40 void dfs1(int u,int pre) 41 { 42 for(int i=head[u];i!=-1;i=edge[i].next) 43 { 44 int v=edge[i].to; 45 if(v==pre) continue; 46 dfs1(v,u); 47 if(smaxn[u]<maxn[v]+edge[i].w) 48 { 49 smaxn[u]=maxn[v]+edge[i].w; 50 smaxid[u]=v; 51 if(smaxn[u]>maxn[u]) 52 { 53 swap(smaxn[u],maxn[u]); 54 swap(smaxid[u],maxid[u]); 55 } 56 } 57 } 58 } 59 void dfs2(int u,int pre) 60 { 61 for(int i=head[u];i!=-1;i=edge[i].next) 62 { 63 int v=edge[i].to; 64 if(v==pre) continue; 65 if(v==maxid[u]) //父节点的最长路径经过v，v不能经过u再经过v，所以要找次长路径 66 { 67 if(smaxn[v]<smaxn[u]+edge[i].w) 68 { 69 smaxn[v]=edge[i].w+smaxn[u]; 70 smaxid[v]=u; 71 if(smaxn[v]>maxn[v]) 72 { 73 swap(smaxn[v],maxn[v]); 74 swap(smaxid[v],maxid[v]); 75 } 76 } 77 } 78 else 79 { 80 if(smaxn[v]<maxn[u]+edge[i].w) 81 { 82 smaxn[v]=edge[i].w+maxn[u]; 83 smaxid[v]=u; 84 if(smaxn[v]>maxn[v]) 85 { 86 swap(smaxn[v],maxn[v]); 87 swap(smaxid[v],maxid[v]); 88 } 89 } 90 } 91 dfs2(v,u); 92 } 93 } 94 int main() 95 { 96 int i,j,k; 97 #ifndef ONLINE_JUDGE 98 freopen("1.in","r",stdin); 99 #endif 100 while(scanf("%d",&n)!=EOF) 101 { 102 init(); 103 int u,w; 104 for(i=2;i<=n;i++) 105 { 106 scanf("%d%d",&u,&w); 107 addedge(i,u,w); 108 addedge(u,i,w); 109 } 110 dfs1(1,-1); 111 dfs2(1,-1); 112 for(i=1;i<=n;i++) 113 { 114 printf("%d ",maxn[i]); 115 } 116 } 117 }