被 *1900 薄纱啦,菜死了www
假设最终答案不小于 \(x\)。如果一个节点上的操作是取 \(\min\),那么它的每个儿子节点的值都需要不小于 \(x\)。否则它至少有一个儿子节点的值不小于 \(x\)。
按照上面的操作,如果我们到达了一个叶子节点,那么就需要填一个不小于 \(x\) 的值。我们只需要找到一种方式,使得最后到达的叶子结点数最少。
设 \(f_i\) 表示以 \(i\) 为根的子树中到达叶子节点的最小数量。
若当前节点是取 \(\max\),那么 \(f_u=\min\limits_{v\in son_u}f_v\)。
否则 \(f_u=\sum\limits_{v\in son_u}f_v\)。
设总共有 \(k\) 个叶子节点,那么答案为 \(k+1-f_1\)。
具体细节看代码。
Code:
#include <bits/stdc++.h>
using namespace std;
const int N = 300005, inf = 0x3f3f3f3f;
int n, k;
int a[N];
int head[N], ver[N], nxt[N], cnt;
int f[N];
void add(int u, int v) {
ver[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}
void dfs(int u) {
bool flag = 0;
if (a[u]) f[u] = inf;
for (int i = head[u]; i; i = nxt[i]) {
int v = ver[i];
flag = 1, dfs(v);
if (a[u]) f[u] = min(f[u], f[v]);
else f[u] += f[v];
}
if (!flag) ++k, f[u] = 1;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 2, x; i <= n; ++i) scanf("%d", &x), add(x, i);
dfs(1);
printf("%d", k + 1 - f[1]);
return 0;
}
标签:nxt,cnt,min,int,head,CF1153D,节点
From: https://www.cnblogs.com/Kobe303/p/16778276.html