HDU 2196 樹形DP Computer

題目鏈接:  HDU 2196 Computer

分析:   先從任意一點開始, 求出它到其它點的最大距離, 然後以該點為中心更新它的鄰點,

           再用被更新的點去更新鄰點......依此遞推 !

代碼:

#include <iostream>   
#include <cstdio>   
#include <cmath>   
#include <cstdlib>   
#include <string>   
#include <cstring>   
#include <algorithm>   
#include <iomanip>   
  
using namespace std;  
const int inf = 0x7FFFFFFF;  
const int maxn = 11111;  
  
struct node{  
    int to, dix, sum;  
    node *next;  
}tree[maxn<<1], *head[maxn];  
  
int ptr, n;   
bool vis[maxn];  
int dp[maxn],h[maxn];  
  
void Init(){  
    ptr=1;  
    memset(dp,0,sizeof(dp));  
    memset(vis,false,sizeof(vis));  
    memset(head,0,sizeof(head));  
}  
  
void AddEdge(int x,int y,int s){  
    tree[ptr].dix=s;  
    tree[ptr].to=y;  
    tree[ptr].next=head[x];  
    head[x]=&tree[ptr++];  
}  
  
void DFS(int cnt){    
    vis[cnt]=true;  
    node *p=head[cnt];  
    while(p!=NULL){  
        if(vis[p->to]) {  
            p=p->next; continue;  
        }  
        DFS(p->to);  
        dp[cnt]=max(dp[cnt],dp[p->to]+p->dix);  
        p->sum=dp[p->to]+p->dix;  
        p=p->next;  
    }  
}  
  
void Tree_Dp(int father, int son){  
    if(vis[son]) return ;  
    vis[son]=true;  
    int Max=0;  
    node* p=head[father];  
    while(p!=NULL){  
        if(p->to!=son)   
            Max=max(Max,p->sum);  
        p=p->next;  
    }  
    p=head[son];  
    while(p!=NULL){  
        if(p->to==father){  
            p->sum=p->dix+Max;  break;  
        }  
        p=p->next;  
    }  
    p=head[son];  
    while(p!=NULL){  
        dp[son]=max(dp[son],p->sum);  
        Tree_Dp(son,p->to);  
        p=p->next;  
    }  
}  
int main(){  
    while(~scanf("%d",&n)&&n){  
        Init();  
        for(int i=2;i<=n;++i){  
            int a,b;  scanf("%d%d",&a,&b);  
            AddEdge(a,i,b);  
            AddEdge(i,a,b);  
        }  
          
        DFS(1);          ///得到1點到其它所有點的距離   
          
        memset(vis,false,sizeof(vis));  
        node* p=head[1];  
        while(p!=NULL){  ///從1的鄰點開始更新   
            Tree_Dp(1,p->to);  
            p=p->next;  
        }  
        for(int i=1;i<=n;++i)  
            printf("%d\n",dp[i]);  
    }  
    return 0;  
}  

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>

using namespace std;
const int inf = 0x7FFFFFFF;
const int maxn = 11111;

struct node{
    int to, dix, sum;
    node *next;
}tree[maxn<<1], *head[maxn];

int ptr, n; 
bool vis[maxn];
int dp[maxn],h[maxn];

void Init(){
    ptr=1;
    memset(dp,0,sizeof(dp));
    memset(vis,false,sizeof(vis));
    memset(head,0,sizeof(head));
}

void AddEdge(int x,int y,int s){
    tree[ptr].dix=s;
    tree[ptr].to=y;
    tree[ptr].next=head[x];
    head[x]=&tree[ptr++];
}

void DFS(int cnt){  
    vis[cnt]=true;
    node *p=head[cnt];
    while(p!=NULL){
        if(vis[p->to]) {
            p=p->next; continue;
        }
        DFS(p->to);
        dp[cnt]=max(dp[cnt],dp[p->to]+p->dix);
        p->sum=dp[p->to]+p->dix;
        p=p->next;
    }
}

void Tree_Dp(int father, int son){
    if(vis[son]) return ;
    vis[son]=true;
    int Max=0;
    node* p=head[father];
    while(p!=NULL){
        if(p->to!=son) 
            Max=max(Max,p->sum);
        p=p->next;
    }
    p=head[son];
    while(p!=NULL){
        if(p->to==father){
            p->sum=p->dix+Max;  break;
        }
        p=p->next;
    }
    p=head[son];
    while(p!=NULL){
        dp[son]=max(dp[son],p->sum);
        Tree_Dp(son,p->to);
        p=p->next;
    }
}
int main(){
    while(~scanf("%d",&n)&&n){
        Init();
        for(int i=2;i<=n;++i){
            int a,b;  scanf("%d%d",&a,&b);
            AddEdge(a,i,b);
            AddEdge(i,a,b);
        }
        
        DFS(1);          ///得到1點到其它所有點的距離
        
        memset(vis,false,sizeof(vis));
        node* p=head[1];
        while(p!=NULL){  ///從1的鄰點開始更新
            Tree_Dp(1,p->to);
            p=p->next;
        }
        for(int i=1;i<=n;++i)
            printf("%d\n",dp[i]);
    }
    return 0;
}