Description

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

Solution

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

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

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

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

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

  • 如何打标记?

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

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

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

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

Code

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