欢迎光临散文网 会员登陆 & 注册

CF竞赛题目讲解_C1709E(深度优先遍历树+路径权值异或)

2022-10-15 12:50 作者:Clayton_Zhou  | 我要投稿

AC代码

https://codeforces.com/contest/1709/submission/176223419

 https://codeforces.com/contest/1709/problem/E

题意:

无根树,点数为 n ,每个点有个点权 a_u。

 定义一条路径 P(u,v)  的权值为经过的所有点的点权的异或和。

 定义一棵树是合法的,当且仅当树上所有简单路径(只经过每个点一次的路径)的权值都不为 0。

 你可以对权值进行修改,可以改成任意正整数,问最少修改多少次才能让这棵树合法。


输出最小修改次数。


题解:

深度优先遍历树+路径权值异或

对每一个点开一个 set 表示当前子树的所有异或和(根节点到当前节点),

v是 u的儿子, 比较set(u)与set(v)是否有相同元素,

有相同元素则需要修改u的权重。


CF竞赛题目讲解_C1709E(深度优先遍历树+路径权值异或)的评论 (共 条)

分享到微博请遵守国家法律