# 动态树中的路径独立性

预估时间限制：1.5 秒。内存限制：256 MB。

实际时限以标准程序在目标环境的最慢用例中位时间乘以 $2$ ，按 $0.5$ 秒向上取整。参考环境见[评测说明](../../../docs/评测环境与性能.md)。

## 背景故事

导航训练器用一棵树记录机器人从基地出发的任务路线，每个站点带有一种信号。管理员会增删路线，并比较各条终点路线末段的相似程度。

(本故事由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

### 输入

```text
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
```

### 输出

```text
2
1
4
5
4
3
```

### 样例 2

### 输入

```text
8
1 0 1 7
1 0 2 7
3 1
2 2
3 1
1 0 2 8
3 2
3 1
```

### 输出

```text
0
2
2
2
```

### 样例 3

### 输入

```text
6
3 0
1 0 100000 0
3 100000
2 100000
3 0
2 0
```

### 输出

```text
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% | 无额外条件 |