P8201题解

__vector__ · 2022-06-14 20:33:30 · 个人记录

思路

设任意一个点 u，dis_{u,x} \oplus dis_{u,y} = k

• 预先转化 u \rightarrow x$ 和 $u \rightarrow y$ 两条路径肯定有一段重复的，然后在 $x \rightarrow y$ 的链上的某个点 $t$ 分开，现在要计算的只剩下 $x \rightarrow y$ 的链上的点。设 $s_i$ 代表根节点到当前点的异或和（$dis_{1,i}$)，一个暂时的答案是 $s_x \oplus s_y
• 上一步中有些还没考虑到
  如 lca_{x,y} 在 x \rightarrow y 的链上，是有贡献的（在 lca_{x,y} 不等于 t 的情况下），但是异或之后没了，所以需要再次异或加上。而 t 是没有贡献的，应该再异或一次删掉（如果 lca_{x,y} = t，那么会导致多异或一下，下面会解释）
• 解释一下上一步
  如果 lca_{x,y} 等于 t（也就是说路径在 lca_{x,y} 分开，这样lca_{x,y} 就没有贡献了）,那么也可以直接异或，因为这样 lca_{x,y} 部分多异或了一下，t 部分多异或了一下，异或两次相当于没异或，又对了
• 总结第二步 $s_x \oplus s_y \oplus w_{lca_{x,y}} \oplus w_t = k

  继续转化：

  w_t = k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}}

问题转化为，x \rightarrow y 的链上是否有一个点，权值是 k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}} ，也就是统计 x \rightarrow y 这条链上权值为 k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}} 的点的数量（注意这个权值仅仅是当前询问对应的！）
对于每一组这样的 x,y ，设 z_i 表示从 1 到 i 点权值为 k \oplus s_x \oplus s_y \oplus w_{lca_{x,y}} 的数量 （注意这个 z_i 仅仅是当前询问对应的 z_i ！），答案就是 z_x + z_y - z_{lca_{x,y}} - z_{lca_{x,y}.father}。把所有询问离线一下，将 x,y,lca_{x,y},lca_{x,y}.father 在树上做一下标记，dfs 的时候集中处理
dfs 具体如下：
dfs 前打标记部分：在树上指定部分标上 +1 或 -1，代表这次询问要加上还是减去这个点的贡献。
dfs 部分：设当前 dfs 到了点 u，那么将该点权值对应的 z_u 乘上该点标记加到对应的询问里去。

最后看每个询问的值是否大于 0 就行了

注意：