hdu 2196 Computer 樹形DP，hdu2196

hdu 2196 Computer 樹形DP，hdu2196

鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=2196

題意:開始有一台電腦，之後添加N-1台電腦(N <= 10000).從第2行到N行有兩個整數a,L，表示第i台電腦和a電腦相連，之間的連線距離為L.

要求的是每台電腦與其他電腦的距離的最大值；

思路:建圖之後DFS,這樣可以求出以每個點為根節點到葉子節點的最大距離；我把在以該點為根的鏈稱為重鏈；

現在來考慮其他情況，同一個父節點，不在重鏈上的點通過父節點到該點更新該點的最大值；

注意:當該點被修改時，以其為根節點的子樹的節點的值都需要修改；即遞推性；只有整棵樹的重鏈上的前面少些點是不需要修改的，不在重鏈上的點，顯然通過重鏈即可更新結果；在重鏈上的點，如果一個節點改變，這條重鏈下面的點都隨之改變；

細節:使用dp[u][2]來u為根節點的最大長度和次大長度。當重鏈最大長度不能改變時，次大長度還是需要改變的。。並且直接賦值即可(無需取max);

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<time.h>
#include<stack>
#include<set>
#include<map>
#include<queue>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define MSi(a) memset(a,0x3f,sizeof(a))
#define inf 0x3f3f3f3f
#define lson l, m, rt << 1
#define rson m+1, r, rt << 1|1
typedef pair<int,int> PII;
#define A first
#define B second
#define MK make_pair
typedef __int64 ll;
template<typename T>
void read1(T &m)
{
    T x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
    if(a>9) out(a/10);
    putchar(a%10+'0');
}
#define N 10010
int dp[N][3],ans[N];
int head[N],tot;
struct Edge{
    int to,w,Next;
    Edge(){}
    Edge(int to,int w,int Next):to(to),w(w),Next(Next){}
}e[N<<1];
inline void ins(int u,int v,int w)
{
    e[++tot] = Edge{v,w,head[u]};
    head[u] = tot;
}
void dfs(int u,int pre)
{
    for(int d = head[u];d;d = e[d].Next){
        int v = e[d].to;
        if(v == pre) continue;
        dfs(v,u);
        if(dp[u][0] <= dp[v][0] + e[d].w){
            dp[u][1] = dp[u][0];
            dp[u][0] = dp[v][0] + e[d].w;
        }
        else if(dp[v][0]+e[d].w > dp[u][1])
            dp[u][1] = dp[v][0] + e[d].w;
    }
}
void solve(int u,int pre)
{
    for(int d = head[u];d;d = e[d].Next){
        int v = e[d].to,w = e[d].w;
        if(v == pre) continue;
        //cout<<u<<" "<<v<<" "<<dp[u][1]<<" "<<dp[u][0]<<endl;
        if(dp[u][1] == -1 || dp[u][0]-w != dp[v][0]) //父節點已改變或者不是重鏈
            dp[v][0] = dp[u][0] + w,dp[v][1] = -1;
        else if(dp[u][0] - w == dp[v][0]){
            if(dp[u][1] + w >= dp[v][0])
                dp[v][0] = dp[u][1] + w,dp[v][1] = -1;
            else dp[v][1] = dp[u][1] + w;//**更新次大的值；
        }
        solve(v,u);
    }
}
int main()
{
    int n;
    while(scanf("%d",&n) == 1){
        int w,v;
        MS0(head);MS0(dp);
        tot = 0;
        rep1(i,2,n){
            read2(v,w);
            ins(i,v,w);ins(v,i,w);
        }
        dfs(1,-1);
        solve(1,-1);
        rep1(i,1,n){
            out(dp[i][0]);
            puts("");
        }
    }
    return 0;
}