题解

1 条题解

  • 1
    @ 2019-07-23 15:47:41
    #include <iostream>
    #include <cstdio>
    using namespace std;
    struct Tree{int l,r;}p[5001];
    int dp[5001][2];
    void Scanf(int &x){
        x=0;char s=getchar();
        while (s<'0'||s>'9')s=getchar();
        while (s>='0'&&s<='9') x=x*10+s-'0',s=getchar();
    }
    void Tree_DP(int id){
        if(!p[id].l)return;
        for(int i=p[id].l;i;i=p[i].r){
            Tree_DP(i);dp[id][0]+=max(dp[i][0],dp[i][1]),
            dp[id][1]+=dp[i][0];
        }
    }
    int main(){
        int n,father,i;
        scanf("%d",&n);
        for(i=1;i<=n;++i)scanf("%d",&dp[i][1]);
        for(i=2;i<=n;++i){
            scanf("%d",&father);
            if(!p[father].l)p[father].l=i;
            else{
                for(father=p[father].l;p[father].r;father=p[father].r);
                p[father].r=i;
            }
        }Tree_DP(1),printf("%d",max(dp[1][0],dp[1][1]));
        return 0;
    }
    
  • 1

信息

ID
1002
难度
2
分类
动态规划 | 树形DP 点击显示
标签
递交数
3
已通过
2
通过率
67%
上传者