1 条题解
-
1⚡root⚡❄⚡root⚡ (tby) LV 8 MOD @ 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