闲话
我看看今天要写什么杂题……
模拟赛
GDKOI2023 Day2。感谢神秘题（咬牙）。
T1
思路不难。三个点间的路径肯定交于一点 \(s\)，我们可以解方程找到 \(s\to u/v/w\) 的长度。
首先对每个点找到前三长的不交链，这个是经典问题，我们可以 \(O(n)\) 地换根 dp 或 \(O(n\log n)\) 线段树。
随后我们需要对每个询问找到是否存在可行的 \(s\)。这是经典三维偏序问题，可以转成二维偏序，排序后用树状数组维护前缀最小值即可。
找到后只需要树上倍增找到 \(u,v,w\) 即可。总时间复杂度 \(O(n\log n)\)。
Submission.
T2
神秘题。设 \(V = 2^{n} - 1\)。
首先纯暴力的复杂度是 \(O(K2^{2n})\) 的。可以发现这个过程能用 FWT 优化，因此做到 \(O(K2^nn)\)。考场上都能推到这里。
题解说答案数组存在线性递推。设转移 \(i\) 次后对 \(x\) 的答案是 \(f(i, x)\)，可以发现 \(f(i)\) 视为一个序列时每位都存在线性递推，即若 \(f(i, x)\) 组成向量 \(\bm f_i\)，有 \(f_i = \sum_{j = 1}^m a_j\times \bm f_{i - j}\)。
这个 \(a_j\) 可以用 BM 算出来。具体地，我们设 \(f'_i = \sum_{j = 0}^{V} r_j f(i, j)\)，其中 \(r_j\) 是个随机数，则 \(f'_i\) 也存在线性递推，和 \(\bm f_i\) 相同。这就是哈希了一下。\(m = O(n)\)，所以我们可以朴素预处理前 \(O(n)\) 个 \(f(i)\)，复杂度是 \(O(n^2 2^n)\) 的。实际上 \(m\) 约为 \(80\)。
因为长度很短，可以随便用什么方法（Fiduccia 甚至矩阵快速幂）算出前 \(m\) 项值贡献的系数，随后对 \(V\) 个值求一下递推即可。
Submission.
T3
不算太神秘的题。下面的东西都是考场上写的。（调整了格式）
不离线可能没法做，我们考虑离线，这样先 dfs 维护完子树内信息，再静态查询。
考虑用长剖合并子树 \(k\) 深度内信息；位运算考虑拆位。
设 \(g(b, \text{id})\) 表示 \(u\) 在长剖数组内的位置是 \(\text{id}\)，\(g(b, \text{id} + k)\) 表示 \(u\) 子树内小于等于 \(k\) 深度的所有点对应的答案在 \(2^b\) 项系数；
\(f(b, \text{id}, 0/1)\) 的定义类似，是 \(\sum v\) 在 \(2^b\) 项系数。
首先考虑统计答案。假设本节点在长剖数组里的位置是 \(\text{id}\)，我们按位统计：
- 如果这一位 \(b\) 高于 \(log_2(最大深度)\)，发现这位不可能被进位，直接统计 \((f(b, \text{id}, 1) - f(b, \text{id}, 0)) \times 2^b\) 即可。
- 如果 \(k > 最大深度\) 直接统计 \(g(b, \text{id}) \times 2^b\) 即可。
- 反之我们需要做进位，先剥离 \(k\) 的低 \(i\) 位和剩下的部分；记低 \(i\) 位是 \(\text{lbit}\)，剩下的部分是 \(\text{hbit}\)，答案首先统计 \((g(b, w) - g(b, w + \text{hbit})) \times 2^b\)。
然后是 \(\text{lbit}\)，我们发现它进位的部分只可能是一个后缀。考虑这个后缀的形态：
如果这个后缀的最高位没到 \(b\) 位，那退化成 1.；
反之这个后缀的长度一定是 \(2^b\)，两次差分即可。
然后考虑计算 \(f\) 和 \(g\)。
首先我们向长儿子递归，数组是连续的，这自然合并了长儿子。然后我们不加更改地对除长链外的儿子做合并，这复杂度是 \(O(n)\) 的。这是两个同等深度的后缀和数组做合并，不需要额外计算信息。
最后对 \(f\) 数组合并进当前节点的贡献，也就是 \(f(i, \text{id}, v_u 第 i 位)\) 自增 \(1\) 并简单地维护 \(f(b, \text{id}, 0/1)\) 处的前缀和性质。
合并完子树贡献后考虑计算当前节点的答案，也就是 \(g\) 函数。
如果没有长儿子，退化成叶子：\(g(b, \text{id}) = f(b, \text{id}, 1)\)。
反之类似上面地统计答案，这时的阈值是长链的长度。
如果当前位超过 \(长链长度\times 2\) 则连进位都不用考虑，直接退化成 \(f(b, \text{id}, 1)\)；
反之讨论进位的范围。这里需要注意的是，最终的进位位置一定形如 111100001111...00001111，我们每次剥离最低的一段 \(1\) 作进位。
如果超过了则只需要考虑最高位的进位，我们仍然有上面的性质，即只考虑最后 \(b\) 个位置的进位。
值就是 \(f(b, \text{id}, 1) - f(b, \text{id} + 2^b, 1) + f(b, \text{id} + 2^b, 0)\)，这里第二次差分不用考虑长度。
如果没超过，我们发现需要统计一段答案在 2^b 项的系数。这是递推的形式，我们要的就是 \(g(b, \text{id} + 2^{b + 1})\)。
值就是 \(f(b, \text{id}, 1) - f(b, \text{id} + 2^b, 1) + f(b, \text{id} + 2^b, 0) - f(b, \text{id} + 2^{b + 1}, 0) + g(b, \text{id} + 2^{b + 1})\)。
Submission.