动态树中的路径独立性：题解¶
出题人解法：反转根到叶序列，按字典序维护叶子，只查询相邻序列的公共前缀。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(q\log q)\) .随机优先级通常给出期望对数高度，但这里不把未界定的重标号工作省略。
3. 精确块代替数值近似¶
参考程序保留反转、叶序及邻居 LCP 框架，使用精确块编号。
令 \(\mathrm{up}[u][k]\) 为向上走 \(2^k\) 条边的节点，\(\mathrm{block}[u][k]\) 表示从 \(u\) 开始的前 \(2^k\) 个权值，只为完整存在的块建立编号。长度一的块用权值加一表示。更长块由两个半块组成：
每层用有序映射将相同二元组映射为同一编号，不同二元组映射为不同编号。由长度归纳，两个块编号相同，当且仅当它们的全部值相同，没有概率性碰撞。
求 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)\) .
参考程序逐条读取并回答，不需要预读未来操作。并列的离线倍增方案预先获得所有实体的排序编号，操作阶段降为对数时间，且省去大量有序映射节点；代价是必须预读并重放整份输入。两者均通过完整范围，离线版在参考测试中峰值约 \(31\) MiB，在线版约 \(109\) MiB；详见评测记录。
图示¶
图展示样例二的三个时刻 \(t\) ：两片同值叶子、删除编号二、再用编号二插入值八。圆中上行为节点编号，下行为权值；蓝色表示当前叶子。\(I(1)\) 是叶子一的独立性。
数据与复现¶
三个样例见题面。生成配方包含十份计分输入；生成器只依赖 Python 标准库，支持 --plan、--out-dir、--case 和 --std。正式大输入及可执行文件不放入发布包。时间和内存的参考测量见性能记录。