CF竞赛题目讲解_CF1778E(dfs + 二进制基)
2023-03-26 10:31 作者:Clayton_Zhou | 我要投稿
AC代码:
https://codeforces.com/contest/1778/submission/199167533
题意:
树有n个节点。树的每个节点u上都写有一个整数au。
但是树没有固定的根,因为它是从天上掉下来的。
鲍勃目前正在研究这棵树。为了增加一些变化,爱丽丝提出了一个游戏。
首先,Bob选择某个节点r作为树的根。然后,爱丽丝选择了一个节点v并告诉他。
然后Bob可以从v的子树中选择一个或多个节点。他的得分将是他选择的节点上写入的所有值的位XOR。
Bob必须找到给定r和v的最大得分。需要找到同一棵树的几种r和v组合的答案。
回想一下,树是一个没有圈的连通无向图。节点u的子树是所有节点y的集合,
使得从y到根的简单路径通过u。注意,u在u的子树中。
题解:
dfs + 二进制基