动态树中的路径独立性¶
预估时间限制：1.5 秒。内存限制：256 MB。
实际时限以标准程序在目标环境的最慢用例中位时间乘以 \(2\) ，按 \(0.5\) 秒向上取整。参考环境见评测说明。
背景故事¶
导航训练器用一棵树记录机器人从基地出发的任务路线，每个站点带有一种信号。管理员会增删路线，并比较各条终点路线末段的相似程度。
(本故事由GPT-6重写)
形式化问题描述¶
维护一棵有根树。初始只有编号为 \(0\) 、权值为 \(0\) 的根节点。结局路径是从根到某个叶子的全部节点权值组成的序列，包括根和叶子。
对于以叶子 \(u\) 结束的序列 \(s_u\) ，定义
\[
I(u)=|s_u|-\max_{v\ne u,\ v\text{ 为叶子}}\operatorname{LCS}(s_u,s_v),
\]
其中 \(\operatorname{LCS}\) 是最长公共后缀的长度。只有一个叶子时，最大公共后缀长度取零。不同叶子的完整序列可以相同，此时独立性可以为零。
依次执行 \(q\) 个操作：
- \(1\ A\ B\ C\) ：在 \(A\) 下增加编号为 \(B\) 、权值为 \(C\) 的儿子。
- \(2\ A\) ：删除 \(A\) 及其整棵子树。
- \(3\ A\) ：查询叶子 \(A\) 的独立性 \(I(A)\) .
删除后的编号可以再用；重新插入的节点是一个新节点。允许删除根，由合法输入保证，这只能发生在最后一个操作。
输入格式¶
第一行一个整数 \(q\) .接下来 \(q\) 行，每行一个操作，格式如上。
输出格式¶
对每个类型 \(3\) 的操作，输出一行一个整数作为答案。
样例¶
样例 1¶
输入¶
14
1 0 1 1
1 0 2 2
1 1 3 2
3 3
3 2
1 0 4 3
1 4 5 3
1 5 6 3
3 6
1 6 7 1
3 7
1 3 8 1
3 7
3 8
输出¶
2
1
4
5
4
3
样例 2¶
输入¶
8
1 0 1 7
1 0 2 7
3 1
2 2
3 1
1 0 2 8
3 2
3 1
输出¶
0
2
2
2
样例 3¶
输入¶
6
3 0
1 0 100000 0
3 100000
2 100000
3 0
2 0
输出¶
1
2
1
样例解释¶
样例一首次比较 \((0,1,2)\) 与 \((0,2)\) ，公共后缀长 \(1\) ，独立性分别为 \(2,1\) .样例二最初有两条相同的 \((0,7)\) ，独立性为零；删除其中一条后，剩余路径独立性为 \(2\) .样例三展示单叶、编号上界和最后删除根的边界。
数据范围与保证¶
\(1\le q\le100000\) .所有节点编号和权值均在 \(0,\ldots,100000\) 内。每次操作的 \(A\) 当前存在；插入的 \(B\) 当前不存在；查询的 \(A\) 为叶子。输入均为整数。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |