题解报告：hdu 2196 Computer（树形dp）

Problem Description

A school bought the first computer some time ago(so this computer's id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.
题解报告：hdu 2196 Computer（树形dp）

Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.

Input

Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space.

Output

For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).

Sample Input

1 1

2 1

3 1

1 1

Sample Output

解题思路：求出树中每个节点能达到的最远距离。对于每个节点u来说，其可能到达的最长距离为max{其子树内的最长距离，其父节点不经过u的子树内的最长距离}。结合树的直径求法(1次dfs)便可得到最长链、每个节点的最长距离dp[u][0]和次长距离dp[u][1]。再一次dfs就是求节点u的反向最长距离即其父节点不经过u的子树内的最长距离dp[u][2]，有两种情况：①如果当前节点v不在树的直径上，那么dp[v][2]的值为max{其父节点u所在子树的最长距离dp[u][0]，其父节点u的父节点不经过u的子树内的最长距离即u的反向距离dp[u][2]}+dist(u,v)；例如5号节点，其dp[5][2]=max{dp[2][0],dp[2][2]}+1(2,5)=[5--2--1--6--7]=3+1=4。②如果当前节点v在树的直径上，那么dp[v][2]的值为max{其父节点u的反向最长距离dp[u][2]，其父节点的次长距离dp[u][1]}+dist(u,v)，例如3号节点，其dp[3][2]=max{dp[2][1],dp[2][2]}+1(2,3)=[3--2--1--6--7]=3+1=4。最后每个节点u能达到的最远距离就是max{正向最长距离dp[u][0]，反向最长距离dp[u][2]}。

AC代码(31ms)：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=10005;
 4 struct node{int to,next,len;}edge[maxn<<1];
 5 int n,x,y,cnt,head[maxn],dp[maxn][3],lgst[maxn];
 6 void add_edge(int u,int v,int w){
 7     edge[cnt].to=v;
 8     edge[cnt].len=w;
 9     edge[cnt].next=head[u];
10     head[u]=cnt++;
11 }
12 int dfs1(int u,int fa){
13     int Dmax=0,Dsec=0;
14     for(int i=head[u];~i;i=edge[i].next){
15         int v=edge[i].to;
16         if(v^fa){
17             int nowd=dfs1(v,u)+edge[i].len;
18             if(nowd>Dmax)lgst[u]=v,Dsec=Dmax,Dmax=nowd;//lgst[u]=v记录u的正向最长路径上的节点v
19             else if(nowd>Dsec)Dsec=nowd;
20         }
21     }
22     dp[u][0]=Dmax,dp[u][1]=Dsec;//记录每个节点的正向最长距离和正向次长距离
23     return Dmax;//返回正向最长距离
24 }
25 void dfs2(int u,int fa){
26     for(int i=head[u];~i;i=edge[i].next){
27         int v=edge[i].to;
28         if(v^fa){
29             if(v==lgst[u])dp[v][2]=max(dp[u][2],dp[u][1])+edge[i].len;
30             else dp[v][2]=max(dp[u][2],dp[u][0])+edge[i].len;
31             dfs2(v,u);
32         }
33     }
34 }
35 int main(){
36     while(~scanf("%d",&n)){
37         cnt=0;memset(head,-1,sizeof(head));
38         memset(dp,0,sizeof(dp));
39         memset(lgst,0,sizeof(lgst));
40         for(int i=2;i<=n;++i){
41             scanf("%d%d",&x,&y);
42             add_edge(i,x,y);
43             add_edge(x,i,y);
44         }
45         dfs1(1,-1);
46         dfs2(1,-1);
47         for(int i=1;i<=n;++i)
48             printf("%d
",max(dp[i][0],dp[i][2]));
49     }
50     return 0;
51 }