Description

给出一棵树,权值未知,但是给出每条边两个端点权值的异或值,求原来的权值。

Solution

  • 假设权值 ,那么从它开始进行一遍 赋值可以得到所有点当前的权值 。当然 不一定等于 ,假设 ,那么真实的

  • 现在给出每个 的范围满足 ,即 ,设 ,等式两边异或上 得到 ,于是 满足

于是现在转化成考虑以下问题:

  • 给出 个限制条件,求出它们之间的交集。(转换成求被覆盖 次的线段长度)

  • 对于每个能够取到符合条件的数字。我们可以用线段差分表示,例如 区间如果满足某个限制条件,那么标记 ,, 这样在遍历 区间的时候得到的权值都是 ,到了 这个点就变成 。那么 个条件都满足,只需要找到哪些点权值为 ,直接找出所有符合条件的线段长度即可。

  • 如何打标记?

直接做 不方便,不妨拆成 ,对于第一个区间 ,符合条件打上 标签,打上 标签,最终 上标签都是 ,符合我们的期望。

  • 关于如何找到可行的区间?

考虑单独一对 的操作,当搜索 时,对 搜索二进制上的每一位,情况无非就是 四种情况,我们规定第一个二进制位表示 ,第二个二进制位表示 ,在保证从高位到低位的情况下,维护当前前缀

  • 当出现 时,因为 当前位为 ,所以对于可选方案可以取 ,当取 时,类似于数位 ,当前不受 限制,后面的数字已经可以随便取了,而当前位异或值为 , 我们可以考虑该位为 的所有数字,于是将这一 的所有数字加入,当取 的时候,该位为 , 不变, 下一层。
  • 当出现 时,因为当前位为 ,可以取 ,同理,取 的时候解除 限制,后面二进制位可以任取搭配,当前位异或值为 ,所以可以加入 ,如果取 的话,异或值为 ,于是 下一层。
  • 当出现 时,因为当前位为 ,任何数字都无法取到,但是异或值为 ,此时 下一层。
  • 当出现 时,因为当前位为 ,任何数字都无法取到,异或值为 ,此时 不变, 下一层。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48324656