# 动态树中的路径独立性：题解

**出题人解法：反转根到叶序列，按字典序维护叶子，只查询相邻序列的公共前缀。GPT-6 提供精确倍增块、编号代际管理、显式子树删除及离线倍增补充方案。**

## 1. 后缀变前缀，只需左右邻居

将根到节点 $u$ 的权值串反转，记为 $r_u$ ，它从 $u$ 沿父亲走到根。原串的最长公共后缀就是反转串的最长公共前缀（LCP）。

把当前叶子的反转串按字典序排序。对某串 $r$ ，与所有其他串的最大 LCP，只可能需要检查其前驱和后继。证明如下：所有具有某个固定前缀的串在字典序中构成连续区间。若某个较远串与 $r$ 共享长度 $k$ 的前缀，它们之间紧邻 $r$ 的串也共享这个前缀。两侧各检查一个即可。

相同完整字符串按唯一内部编号打破排序平局，使容器保留每片叶子。相同串之间的 LCP 是完整长度，所以独立性可以为零。没有邻居时最大 LCP 取零。

## 2. 出题人的有序结构与倍增比较

反转串满足 $r_u=(a_u,r_{\operatorname{parent}(u)})$ .因此可按“当前值、父亲反转串的顺序”作为字典序键。

出题人实现用两棵随机 Treap：一棵包含所有当前节点，为父串提供顺序标签；另一棵只含叶子，用来找前驱、后继。插入第一名儿子时把父亲从叶集合删除；删除子树后若父亲失去最后一名儿子，则重新插入父亲。倍增记录向上 $2^k$ 个值的哈希，在查询时从大块到小块比较，以求 LCP。

这一方案依赖标签始终保持严格顺序、相等判定不发生哈希碰撞。浮点区间中点和三重哈希是其具体数值表示，不能替代精确性的证明。Treap 旋转后的标签重分配还会遍历相关子树。

若有 $I$ 次节点插入/删除、$Q$ 次查询，最大 Treap 高度为 $h$ ，标签重分配共访问 $R_{\rm label}$ 个节点，则其工作量可写为
$$
O(Ih+Q(h+\log q)+R_{\rm label}),
$$
倍增空间为 $O(q\log q)$ .随机优先级通常给出期望对数高度，但这里不把未界定的重标号工作省略。

## 3. 精确块代替数值近似

参考程序保留反转、叶序及邻居 LCP 框架，使用精确块编号。

令 $\mathrm{up}[u][k]$ 为向上走 $2^k$ 条边的节点，$\mathrm{block}[u][k]$ 表示从 $u$ 开始的前 $2^k$ 个权值，只为完整存在的块建立编号。长度一的块用权值加一表示。更长块由两个半块组成：
$$
\left(\mathrm{block}[u][k-1],
\mathrm{block}[\mathrm{up}[u][k-1]][k-1]\right).
$$
每层用有序映射将相同二元组映射为同一编号，不同二元组映射为不同编号。由长度归纳，两个块编号相同，当且仅当它们的全部值相同，没有概率性碰撞。

求 LCP 时从大到小枚举 $k$ ：若两个剩余串均至少有 $2^k$ 项且块编号相同，就同时向上跳过该块。最后累计长度即为 LCP，耗时 $O(\log q)$ .

比较两个完整反转串时，先求 LCP；若其中一个已结束，较短串更小，否则比较下一项权值；完全相同时比较内部编号。以该比较器维护有序叶集合，可以精确查找、插入和删除。

## 4. 编号复用与删除

每次插入分配一个全新的内部编号，外部题目编号只负责找到当前实体。已删除的旧实体不能因外部编号复用而复活。

保存内部实体的儿子表，删除子树时用显式栈，只处理仍活着的实体，删除其中的叶子并清除外部映射。删除后，更新外部父亲的活儿子数，必要时把它加入叶集合。旧儿子记录可保留；每条创建边在其父实体被删除时最多扫描一次，遇到已删除儿子直接略过。

祖先链的块在创建时就固定，删除整棵子树不会改变任何存活节点的祖先链。故有序集合里已有键的相对顺序永远不变。根也按实际子树删除；合法输入中此后没有操作。

## 5. 正确性与复杂度

精确块归纳保证 LCP 和比较器正确；生命周期维护保证集合恰好包含当前叶子；邻居性质保证查询取得所有其他叶子的最大 LCP。用路径长度减去该值便得到所求独立性。

创建的实体总数至多 $q+1$ .每次插入建立 $O(\log q)$ 个块，每次有序映射操作耗时 $O(\log q)$ ；集合比较耗时 $O(\log q)$ ，树上查找再需 $O(\log q)$ 次比较。所有子树删除合计仅访问创建过的实体和边。因此总时间 $O(q\log^2 q)$ ，空间 $O(q\log q)$ .

[参考程序](std.cpp)逐条读取并回答，不需要预读未来操作。并列的[离线倍增方案](solution-alternative-offline.zh.md)预先获得所有实体的排序编号，操作阶段降为对数时间，且省去大量有序映射节点；代价是必须预读并重放整份输入。两者均通过完整范围，离线版在参考测试中峰值约 $31$ MiB，在线版约 $109$ MiB；详见[评测记录](../../../docs/benchmark-R29.json)。

## 图示

图展示样例二的三个时刻 $t$ ：两片同值叶子、删除编号二、再用编号二插入值八。圆中上行为节点编号，下行为权值；蓝色表示当前叶子。$I(1)$ 是叶子一的独立性。

![算法示意图](assets/example.svg)

## 数据与复现

三个样例见题面。[生成配方](tests/plan.json)包含十份计分输入；[生成器](tests/generate.py)只依赖 Python 标准库，支持 --plan、--out-dir、--case 和 --std。正式大输入及可执行文件不放入发布包。时间和内存的参考测量见[性能记录](../../../docs/benchmark-R29.json)。