HDU 1520 樹形DP

分析:  雖然看一去是有向邊, 但完全可以用無向邊去做!

#include<iostream>  
#include<cstdio>  
#include<cstring>  
 
using namespace std; 
const int maxn=6010; 
 
struct node{ 
    int v; 
    node *next; 
}tree[maxn<<1],*head[maxn]; 
 
int n,ptr; 
bool vis[maxn]; 
int dp[maxn][2],val[maxn]; 
 
void Init(){ 
    ptr=1; 
    memset(vis,false,sizeof(vis)); 
    memset(dp,0,sizeof(dp)); 
    memset(head,0,sizeof(head)); 
} 
 
void AddEdge(int x,int y){ 
    tree[ptr].v=y; 
    tree[ptr].next=head[x]; 
    head[x]=&tree[ptr++]; 
} 
 
void DFS(int cnt){ 
    vis[cnt]=true; 
    dp[cnt][1]=val[cnt]; 
    node *p=head[cnt]; 
    while(p!=NULL){ 
        if(vis[p->v]){ 
            p=p->next; continue; 
        } 
        DFS(p->v); 
        dp[cnt][1] += dp[p->v][0]; 
        dp[cnt][0] += max(dp[p->v][1], dp[p->v][0]); 
        p=p->next; 
    } 
} 
 
int main(){ 
    while(~scanf("%d",&n)&&n){ 
        Init(); 
        for(int i=1;i<=n;++i) 
            scanf("%d",val+i); 
        int a,b; 
        while(scanf("%d%d",&a,&b)&&a+b){ 
            AddEdge(a,b); 
            AddEdge(b,a); 
        } 
        DFS(1); 
        printf("%d\n",max(dp[1][0],dp[1][1])); 
    } 
    return 0; 
}