标签：text 个数 XorDistances 异或 oplus dis

[ABC201E] Xor Distances

首先，根据 \(a\oplus a=0\)，一条路径 \(dis(u,v)=(dis(1,\text{LCA})\oplus dis(1,u))\oplus(dis(1,\text{LCA})\oplus dis(1,v))\)，消去相同的，得 \(dis(1,u)\oplus dis(1,v)\)。

预处理从 \(1\) 到每个点的前缀异或，问题被转换成从 \(n\) 个数中选两个两两异或的总和。

按照位考虑，将每个数拆成 \(60\) 位，记录到数组中，令 \(one_i\) 表示 \(n\) 个数中第 \(i\) 位为 \(1\) 的数。

然后枚举每一个数，对于每一位的答案为与它这一位不同的数的个数 \(\times\) 这一位的权值。

复杂度 \(O(60n)\)。

注意位运算的取模，即 \((1<<60)\times n\) 可能爆炸，需要先取模。

代码

标签：text,个数,XorDistances,异或,oplus,dis
From： https://www.cnblogs.com/wscqwq/p/17596106.html