题解：CF1153D Serval and Rooted Tree

题目传送门
首先，我们先考虑二分一个

\text{{mid}}

，检查“根结点的最大值会不会

\ge \text{{mid}}

”。那么对于叶子结点

[1,k]

的值，就可以化为

0

和

1

，表示这个值是不是

\ge \text{mid}

。要使根结点的值尽可能大，就要使

1

的使用次数尽可能小，所以设

dp_{i}

表示以

i

为根的子树中叶子结点最少使用多少个

1

，才能使

i

这个点的值为

1

。先考虑

i

点的操作为取

\min

：

i

的儿子一定都要是

1

，所以

dp_{i}=\sum \limits_{j} dp_{j}

（其中

j

为

i

的儿子）。再考虑

i

点的操作为取

\max

：

i

的儿子只要有一个为

1

即可，所以

dp_{i}=\min \limits_{j} \{ dp_{j} \}

（其中

j

为

i

的儿子）。列出转移方程，我们发现貌似没有用到

\text{mid}

，所以把二分去掉，答案就为

k-dp_{1}+1

。
code:

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,m,opt[N],dp[N];
vector<int> e[N];

void dfs(int x)
{
	if(e[x].size()==0)
	{
		dp[x]=1;
		return ;
	}
	int ans1=1e9,ans2=0;
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		dfs(y);
		ans1=min(ans1,dp[y]),ans2+=dp[y];
	}
	if(opt[x]) dp[x]=ans1;
	else dp[x]=ans2;
	return ; 
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",opt+i);
	for(int i=2;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		e[x].push_back(i);
	}
	for(int i=2;i<=n;i++) m+=(e[i].size()==0);
	dfs(1);
	cout<<m-dp[1]+1;
	return 0;
}

题解：CF1153D Serval and Rooted Tree

文章操作

相关推荐

评论

题解：CF1153D Serval and Rooted Tree