题目链接：https://cn.vjudge.net/contest/277955#problem/B
题目大意：首先输入n代表有n个电脑，然后再输入n-1行，每一行输入两个数，t1,t2.代表第（i+1）个电脑连向电脑t1，花费是t2，然后问你每个电脑的到其他电脑的最大花费。
具体思路：按照图来想，对于节点2，最大的花费的路径可能有两种，第一种，往下遍历他的叶子节点找到最大的，第二种，先往上走，然后从往上走的节点再去找最大的花费。
对于第一种花费，我们直接dfs求就可以了。 但是在求的时候顺便求一下当前这个节点往下的第二大花费，具体作用是在第二种情况中会使用到。
对于第二种花费，我们先是往上移动，然后再去求他上面的点的最大花费，但是这个地方要注意一点，在往上面走的时候，求的最小花费可能会有路径重复，比如说三号节点，往上走的话是2号节点，而二号节点的最远距离有可能是2->3->4，这样的话，就会有一段路径重复计算。这个时候求的次小花费就能有用处了，既然我花费最大的用不了，那么我就用花费第二小的。
状态转移方程： 对于第二种情况,如果当前的节点的父亲节点的最大花费的路径中包括当前这个节点，这个时候我们就算上第二大的，然后再加上当前这个点到父亲节点的花费就可以了。否则就安最大花费计算。
AC代码：
1 #include<iostream> 2 #include<cmath> 3 #include<stack> 4 #include<stdio.h> 5 #include<algorithm> 6 #include<queue> 7 #include<vector> 8 #include<cstring> 9 using namespace std; 10 # define inf 0x3f3f3f3f 11 # define ll long long 12 const int maxn = 4e4+100; 13 struct node 14 { 15 int nex; 16 int to; 17 int cost; 18 } edge[maxn]; 19 int num,head[maxn],dp[maxn][3],father[maxn]; 20 void init() 21 { 22 num=0; 23 memset(head,-1,sizeof(head)); 24 memset(dp,0,sizeof(dp)); 25 } 26 void addedge(int fr,int to,int cost) 27 { 28 edge[num].to=to; 29 edge[num].nex=head[fr]; 30 edge[num].cost=cost; 31 head[fr]=num++; 32 } 33 void dfs1(int st,int rt) 34 { 35 for(int i=head[st]; i!=-1; i=edge[i].nex) 36 { 37 int to=edge[i].to; 38 if(to==rt) 39 continue; 40 dfs1(to,st); 41 if(dp[to][0]+edge[i].cost>dp[st][0]) 42 { 43 father[st]=to;// 这个地方要注意是谁是数组的下标，我们需要判断的是这个父亲节点的路径上是不是包括这个子节点。 44 dp[st][1]=dp[st][0];//记录次大的 45 dp[st][0]=dp[to][0]+edge[i].cost; 46 } 47 else if(dp[to][0]+edge[i].cost>dp[st][1]) 48 { 49 dp[st][1]=dp[to][0]+edge[i].cost; 50 } 51 } 52 } 53 void dfs2(int st,int rt) 54 { 55 for(int i=head[st]; i!=-1; i=edge[i].nex) 56 { 57 int to=edge[i].to; 58 if(to==rt) 59 continue; 60 if(father[st]==to) 61 { 62 dp[to][2]=max(dp[st][1],dp[st][2])+edge[i].cost; 63 } 64 else 65 dp[to][2]=max(dp[st][2],dp[st][0])+edge[i].cost; 66 dfs2(to,st); 67 } 68 } 69 int main() 70 { 71 int n; 72 while(~scanf("%d",&n)) 73 { 74 init(); 75 int t1,t2; 76 for(int i=2; i<=n; i++) 77 { 78 scanf("%d %d",&t1,&t2); 79 addedge(i,t1,t2); 80 addedge(t1,i,t2); 81 } 82 dfs1(1,-1); 83 dfs2(1,-1); 84 for(int i=1; i<=n; i++) 85 { 86 printf("%d ",max(dp[i][0],dp[i][2])); 87 } 88 } 89 return 0; 90 } 91