题目链接
https://codeforces.com/problemset/problem/1153/D
题目大意
题目思路
定义dp[u]为u节点在其子树中的排名为多少? !太妙了!
题目代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#define ll long long
const int inf = 0x7fffffff;
const int N = 3e5 + 5;
using namespace std;
int n,k;
int op[N],fa[N],s[N],dp[N];
vector<vector<int>>g(N);
void dfs1(int u,int fa)
{
for(int v:g[u])
{
if(v == fa) continue;
dfs1(v,u);
s[u] += s[v];
}
// 如果是叶子节点
if(g[u].size() == 1 && u != -1){
s[u] = 1;
dp[u] = 1;
}
return;
}
void dfs2(int u,int fa)
{
if(g[u].size() == 1 && u != -1) return;
if(op[u] == 1){
dp[u] = inf;
for(int v:g[u])
{
if(v == fa) continue;
dfs2(v,u);
dp[u] = min(dp[u],dp[v]);
}
}else{
for(int v:g[u])
{
if(v == fa) continue;
dfs2(v,u);
dp[u] += dp[v];
}
}
}
int main()
{
cin >> n;
for(int i = 1;i <= n;++i) cin >> op[i];
for(int i = 2;i <= n;++i){
int x;cin >> x;
g[x].push_back(i);
g[i].push_back(x);
}
dfs1(1,0);dfs2(1,0);
cout << s[1] - dp[1] + 1 << '\n';
return 0;
}
标签:dfs2,int,fa,continue,值求,可变,排名,include,dp
From: https://www.cnblogs.com/gebeng/p/18148224