CF1153D. Serval and Rooted Tree

题目链接：CF1153D

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3*1e5+7;
const int inf = 0x3f3f3f3f;
int n,node[maxn],k,dp[maxn];
//dp[i]=a 表示取 K..1中第a个时，节点i表示的值最大
vector<int> son[maxn];
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)cin>>node[i];
    for(int j,i=2;i<=n;++i){
        cin>>j;
        son[j].push_back(i);
    }
    for(int i=n;i>=1;--i){
        if(son[i].empty()){
            k++;
            dp[i]=1;
            continue;
        }
        if(node[i]==1){
            dp[i]=inf;
            for(vector<int>::iterator it=son[i].begin(); it!=son[i].end(); ++it){
                dp[i] = min(dp[i],dp[*it]);
            }
        }else{ //node[i]==0
            dp[i]=0;
            for(vector<int>::iterator it=son[i].begin(); it!=son[i].end(); ++it){
                dp[i]+= dp[*it];
            }
        }
    }
    cout<<k+1-dp[1]<<endl;
    return 0;
}