POJ2342--Anniversary party Tree DP

huangboyan · 2018-08-11 14:09:01 · 个人记录

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=6000+10;
int a[maxn],fa[maxn],f[maxn][2],p[maxn],n,vis[maxn];
inline void dfs(int x){
    p[x]=1;
    for(register int i=1;i<=n;i++){
        if(p[i]==0 && fa[i]==x){
            dfs(i);
            f[x][1]+=f[i][0];
            f[x][0]+=max(f[i][0],f[i][1]);
        }
    }
}
int main(){
    int i,j,k,m,t;
    scanf("%d",&n);
    memset(fa,0,sizeof(fa));
    memset(p,0,sizeof(p));
    memset(f,0,sizeof(f));
    memset(vis,0,sizeof(vis));
    for(register int i=1;i<=n;i++)
        scanf("%d",&a[i]);  
    for(register int i=1;i<=n;i++)
        f[i][1]=a[i];
    while(scanf("%d%d",&t,&k) && t!=0 && k!=0){
        fa[t]=k;
        vis[t]=1;
    }
    for(register int i=1;i<=n;i++){
        if(vis[i]==0){
            k=i;
            break;
        }
    }
    //memset(p,0,sizeof(p));
    dfs(k);
    printf("%d\n",max(f[k][0],f[k][1]));
    return 0;
}

只过了POJ，HDU毒瘤TLE