CF1902F Trees and XOR Queries Again 题解

· · 题解

前言

本题是简单的、一眼的、普通的、显然的。

正文

0x00 分析题目

给定一颗带点权无根树，每次询问给定两个点 u,v 和参数 k，回答是否有一个 u\leftarrow v 简单路径的点权子集其异或和是 k。

可以肯定的是这个题需要线性基，以及线性基合并等知识，不会的推荐线性基学习笔记 | Menci's OI Blog。下文默认 n,q 同阶。

0x01 树上倍增 \mathcal{O}\left(n\log^3{n}\right)

做法

首先考虑到一个显然的做法，树上倍增，对于每个 u 处理出 B_{u,k} 表示 u 到其 2^k 级祖先这条链的线性基，和普通树上倍增一样只不过合并两个 2^{k-1} 的信息时用线性基合并，则预处理时间复杂度 \mathcal{O}\left(n\log^3{n}\right)。

询问时，u,v 不断向上倍增跳，直到其 lca 的位置，这样一共需要合并 \mathcal{O}\left(\log{n}\right) 个线性基，单次询问时间复杂度 \mathcal{O}\left(\log^3{n}\right)。

代码实现

实测使用一定的常数优化可以轻松通过：

  1. 线性基插入一个数 x 时从 \log_2 x 位开始枚举，每次插入后重新取 \log_2 x 寻找下一位。
  2. 树上倍增时从 \log dep 开始倍增。
  3. 取 \log_2 x 使用 31^__builtin_clz(x) 计算最快。

AC CODE，最大点跑了 6114 ms。

0x02 点分治做法 \mathcal{O}\left(n\log^2{n}\right)

做法

观察发现树上倍增做法之所以慢是应为我们钦定了两个点在他们的 lca 处相遇然后合并线性基，所以需要预处理和查询很多东西。但是对于这个这个题他是无根树，不需要一定在 lca 处才能算。这启发我们使用点分治来处理树上询问。

具体的，对于每次点分治，处理跨越当前子树重心的所有询问。对于每个子树的点 u 处理出其到重心链上的线性基，这一部分不需要线性基合并，只需要直接继承他父亲的线性基然后加入 u 的点权即可。处理查询时合并以 u 到重心的线性基和 v 到重心的线性基即可。单次查询时间复杂度 \mathcal{O}\left(\log^2{n}\right)，点分治的时间复杂度 \mathcal{O}\left(n\log^2{n}\right)。

思考，点分治的好处是每次查询只需要合并两个线性基，并且预处理不需要合并线性基所以可以得到更优的时间复杂度。

代码实现

加上前面的优化甚至可以跑进一秒，AC CODE。

总结

本题利用了点分治对询问优秀的拆分方式解决了本题。