题目大意

给定一个有 n 个结点的以 1 为根的树，每个结点上有一个操作类型 0 或 1 。

操作类型 0 代表该节点的权值为其所有儿子的权值的最小值，操作类型 1 代表该节点的权值为其所有儿子的权值的最大值。叶子结点的权值没有意义，可以忽略。

假设这棵树有 k 个叶子，你需要在每个叶子上填入数字 1−k ，使得按如上计算结点权值后，结点 1 的权值最大，输出这个最大值。

解题思路

假设答案为，如果一个结点上的操作为，则其要求其每个儿子结点的值都大于，如果一个结点上的操作为，其要求其中一个儿子结点的值大于。按照上面的操作，如果我们到达了一个叶子结点，那么我们就需要一个大于等于的数来填入这个格子中，由于在遍历全树时不会改变，我们只需要找到一种方式，使得最后到达的叶子结点数最少。我们发现在这个过程中唯一能控制到达叶子结点数的是操作类型，在计算该节点信息的过程中，我们只需选择一个叶子结点数最小的子树，即对其所有儿子能选择的最小叶子节点数取。在操作时，由于其要求每个儿子结点的值都大于，我们要对其儿子能选择的最小叶子结点数求和，作为该节点能选择的最小叶子结点数。最后，我们发现根节点能选择的最小叶子结点数是和无关的，而这个结点数的意义是至少需要选择个值大于等于的数，那么我们的最大为。

代码展示

CPP

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=600010;
int n,op[maxn],x,k;
int cur,h[maxn],nxt[maxn],p[maxn];
int f[maxn];
void add_edge(int x,int y)
{
	cur
++;
	nxt
[cur]=h[x];
	h
[x]=cur;
	p
[cur]=y;
}
void dfs(int x,int fa)
{
	int ch=0;
	if(op[x]==1)f[x]=2e9;
	for(int j=h[x];j;j=nxt[j])if(p[j]!=fa)
	{
		ch
++;
		dfs(p[j],x);
		if(op[x]==0)f[x]+=f[p[j]];
		else f[x]=min(f[x],f[p[j]]);
	}
	if(!ch)k++,f[x]=1;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",op+i);
	for(int i=2;i<=n;i++)scanf("%d",&x),add_edge(i,x),add_edge(x,i);
	dfs(1,-1);
	printf("%d\n",k+1-f[1]);
	return 0;
}

题解：CF1153D Serval and Rooted Tree

文章操作

题目大意

解题思路

代码展示

相关推荐

评论

题解：CF1153D Serval and Rooted Tree