题解：P16501 【MX-S14-T4】「KWOI R2」神秘树
Cybher
·
·
题解
出题人题解。
数据太难造了，放过许多错解。
我们先对树的形态做出一定推导。
假如我们固定根为 rt。
那么对于任意点 u，我们观察一下 u 和 rt 的关系式子，令 mx(u) 表示 u 到根链的点编号最大值。
因为 $S_{rt}\oplus rt$ 一定是个定值，我们姑且认为这个值是 $C$。
所以我们就能得到 $S_u=C\oplus mx(u)$。
然后我们就能推出下面两个事实：
1. 对于点 $u$，最多存在一个儿子 $v$ 编号比他大。
假设有两个儿子 $v_1$，$v_2$ 的编号均比他大，我们计算一下 $v_1$ 和 $v_2$ 的贡献有：
$S_{v_1}\oplus S_{v_2}=C\oplus mx(v_1)\oplus C\oplus mx(v2)=v_1\oplus v_2$。
$lca(u,v)\oplus mx(u,v)=u\oplus \max(u,v)$ 一定不等于 $v_1\oplus v_2$ 矛盾了。
2. 如果点 $u$ 不是它到根链中的最大值，一定不存在儿子编号比他大。
假如存在儿子 $v$ 编号比他大，我们计算一下 $u$ 和 $v$ 的贡献有：
如果 $v$ 也不是根链最大值有：$S_u\oplus S_v=0$。
否则 $S_u\oplus S_v=X\oplus v$，$X$ 为任意一个不是 $u$ 的数。
然而 $lca(u,v)\oplus mx(u,v)=u\oplus v$，这一定不等于上面算出来的结果，矛盾了。
所以我们就发现这个树的形态其实是有一条编号递增的主链，然后主链上每个点都再挂上一个大根堆，堆内的点由于到根链路径最大值都一样，所以子树大小也均一样。
然后就可以写各种不用的暴力 dp 了，可以实现出 $O(n^4)$，$O(n^3)$，$O(\frac{n^3}{w})$ 等不同时间复杂度做法，获得不同部分分
讲解 $O(n^2)$ 的做法。
我们现在需要判断一段区间是否可能成为一段合法子树。首先这棵子树的根一定为区间的右端点，我们认为这个点不在递增主链上。
假设 $i$ 有 $c$ 个儿子，并且每个儿子的子树的和都为 $t$。那么就有：
在模 $n$ 意义下，$P_i+c\times t=t$。或者说 $c\times t=t-P_i$。
假设我们从左往右扫描这个序列，想要建造 $i$ 的这棵树，也就需要耗费它前面的 $c$ 棵树。
我们可以求出 $c$ 最小是多少，令其为 $f_{t,i}$。
具体地若 $t=0$，当 $P_i=0$ 则 $f_{t,i}=0$，否则无解。
$t\neq 0$ 时，方程有解当且仅当 $t-P_i$ 被 $\gcd(t,n)$ 整除（裴蜀定理）。
根据裴蜀定理，能解出 $c$ 的最小值为 $\frac{t-P_i}{g}\times(\frac{t}{g})^{-1}\mod (n/g)$。
接下来我们要考虑主链点的情况，假设 $l$ 是固定的，我们判断 $l$ 到 $i$ 这段区间是否能够组成若干个子树，每个子树的和都是 $l$ 的后缀和。我们从 $l$ 到 $n$ 枚举 $i$ 并且维护当前子树个数，每次让 $i$ 贪心吞掉前面 $f_{t,i}$ 个子树，并产生一个新子树，因为一定前面子树越多越容易合法。直到前面的子树不够或者无解就停止。如果 $i$ 合法则记录 $g_{l,i}=1$。
最后我们枚举根作为主链点的第一个点 $i$，记录 $l$ 代表 $l$ 到 $n-1$ 这段区间都是主链点的子树,，初始 $l$ 为 $0$。
首先一定要有 $g_{l,i}=1$，否则不合法。
然后主链的第二个点其实已经定了，为 $suf_{l}\oplus rt\oplus suf_{rt+1}$，$suf$ 是后缀和，一直做下去判下去就好了。
还能再给力吗，我们分析一下瓶颈，主要在于枚举根和求 $g$，我们分别做优化。
先说枚举根这里，其实这里复杂度没有问题。
首先假如固定根 $u$ 是主链点，上一个主链点是 $v$，上上个主链点是 $w$，那么 $u\oplus suf_{v+1}$ 是定值。
因为 $u=suf_{v+1}\oplus v \oplus suf_{w+1}$。可以得到 $u\oplus suf_{v+1}=v\oplus suf_{w+1}$。我们设这个定值为 $C$，根选什么也能根据 $C$ 确定出来。
我们要证明原来的枚举根的暴力复杂度复杂度上界就是 $O(n\sqrt n)$ 的。
考虑原来枚举根的算法流程，假如我们枚举 $C$，然后从当前点 $u$ 跳到了 $u+d$ 步。
假如 $d>\sqrt n$，那么每种 $C$ 这种类型的步最多只有 $\sqrt n$ 种，所以复杂度没有问题。
假如 $d<\sqrt n$，假如 $u$ 固定， $C$ 不同，跳的步一定不同。$d<\sqrt n$ 的话，终点也最多只有 $\sqrt n$ 种，所以复杂度没有问题。
然后讲解如何快速求 $g$，不妨把 $g$ 数组改成 $lim_i$ 代表能使 $g_{i,x}=1$ 的最大的 $x$。
首先根据之前求 $g$ 的过程，第一个点必须要满足 $f_{t,x}=0$，也就是说 $P_x=suf_{x-1}$，所以有 $suf_{x}=0$。
因此若 $x=n-1$，$lim_x=n-1$。
若 $suf_{x+1}\neq0$，$lim_x=x$。
否则令 $s=P_x$。
若 $S=0$，所有点的子树和都要为 $0$，$lim_x$ 为第一个非 $0$ 点。
若 $S\neq0$，扫描 $P_i=0$ 的点有 $f_{t,p_i}=1$，不会对当前树的个数有影响可以跳过，所以我们只需要处理非零点。
我们考虑根号分治，对于某个 $s$，若出现的次数 $>B$，我们预处理整条非零点序列上的 $f$ 的前缀和，单调栈求出每个起点第一次失败的位置。一起就做完了，否则就直接扣除 $0$ 点做暴力，每次扫描如果遇到 $P_i=s$ 就会使树的个数多一个，遇到其他值至少会让树的个数 $-1$ 或者减没直接失败。所以复杂度是对的。
最后时间复杂度 $O(n\sqrt n)$。