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的权重。