CodeForces1153D Serval and Rooted Tree 树形DP 贪心

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeForces1153D Serval and Rooted Tree 树形DP 贪心，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1246字，纯文字阅读大概需要2分钟。

内容图文

CodeForces1153D Serval and Rooted Tree 树形DP 贪心

题意

\(n\)个以\(1\)为根的一棵树，每个非叶子结点都有一个操作\(max\)或者\(min\)(0表示\(min\),1表示\(max\))， 表示这个节点中的值应该分别等于其子节点的所有值中的最大值或者最小值。假设这棵树有\(k\)个叶子节点，你可以将每个节点填上\([1,k]\)的数字，且每个数组只能使用一次，问根节点的最大值是多少

\[2 \leq n \leq 3\times10^5 \]

分析

一道比较难且有意思的贪心题

考虑这里\(max\)和\(min\)的性质

发现\(min\)要使所有子节点的值尽可能大，\(max\)要使子节点的最大值尽可能大，尽可能大这个问题又可以递归到叶子节点层来讨论

所以我们可以说\(min\)的所有儿子影响其值，\(max\)我们可以自行选择一个儿子来影响

由此得出贪心：对于非叶子节点，若是\(min\)则影响该点的个数为该节点所有子节点值的叶子节点个数和，若是\(max\)节点影响该点的叶子节点个数是所有儿子里的最小值

最后，若有\(k\)的儿子影响根的值，那么答案就是\(n - k + 1\),然后就可以DP了

代码

const int maxn = 3e5 + 5;
vector<int> e[maxn];
int a[maxn],d[maxn];
int cnt,n;

void dfs(int u){
	if(e[u].empty()) {
		d[u] = 1;
		cnt++;
		return;
	}
	d[u] = a[u] ? n : 0;
	for(auto v:e[u]){
		dfs(v);
		if(a[u]) d[u] = min(d[u],d[v]);
		else d[u] += d[v];
	}
}

int main(){
	n = rd();
	for(int i = 1;i <= n;i++)
		a[i] = rd();
	for(int i = 2;i <= n;i++){
		int x = rd();
		e[x].push_back(i);
	}
	dfs(1);
	printf("%d",cnt + 1 - d[1]);
}

内容总结

以上是互联网集市为您收集整理的CodeForces1153D Serval and Rooted Tree 树形DP 贪心全部内容，希望文章能够帮你解决CodeForces1153D Serval and Rooted Tree 树形DP 贪心所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---