首页 > 其他分享 >CF1153D

CF1153D

时间:2022-10-11 10:14:51浏览次数:51  
标签:nxt cnt min int head CF1153D 节点

被 *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

相关文章