CF Round #551 (Div. 2) D

CF Round #551 (Div. 2) D

链接

https://codeforces.com/contest/1153/problem/D

思路

不考虑赋值和贪心，考虑排名。
设\(dp_i\)是子树i中的i是第dp_i大的(相同大小放在后面)。
\(opt=1,dp_u=max(dp[v])(v\in G)\)
\(opt=0,dp_u=\sum\limits _{v\in G}{dp[v]}\)
dp[1]是1到k中第dp[1]大的，就是k-dp[1]+1
然后\(ans=k-dp[1]+1\)

代码

#include <bits/stdc++.h>
using namespace std;
const int N=4e5+7;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
int n,opt[N],dp[N],js;
vector<int> G[N];
void dfs(int u) {
    if(!G[u].size()) return dp[u]=1,++js,void();
    if(opt[u]) dp[u]=0x3f3f3f3f;
    for(auto v:G[u]) {
        dfs(v);
        if(opt[u]) dp[u]=min(dp[u],dp[v]);
        else dp[u]+=dp[v];
    }
}
int main() {
    n=read();
    for(int i=1;i<=n;++i) opt[i]=read();
    for(int i=2,x;i<=n;++i) x=read(),G[x].push_back(i); 
    dfs(1);
    cout<<js-dp[1]+1<<"\n";
    return 0;
}