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;
}