[ICPC2021 Macao R] Colorful Tree

**【题目描述】** 你的任务是维护一棵有色树并处理查询。 一开始，树上只有一个编号为 $1$ 的顶点，颜色为 $C$。然后按顺序进行 $q$ 个操作，有两种类型： - $0$ $x$ $c$ $d$：向树中添加一个颜色为 $c$ 的新顶点，其编号为 $(n+1)$，其中 $n$ 是当前存在的顶点数。同时，添加一条连接顶点 $x$ 和 $(n+1)$ 的长度为 $d$ 的边。 - $1$ $x$ $c$：将顶点 $x$ 的颜色更改为 $c$。 在每次操作之后，你应该找到当前树中颜色 $\textbf{不同}$ 的两个顶点 $u$ 和 $v$（$1 \le u, v \le n$），使得它们之间的距离尽可能大。 两个顶点 $u$ 和 $v$ 之间的距离是树上从 $u$ 到 $v$ 的最短路径的长度。 **【输入格式】** 输入的第一行包含两个整数 $q$ 和 $C$（$1 \le q \le 5 \times 10^5$，$1 \le C \le q$），表示操作的数量和顶点 $1$ 的初始颜色。 接下来的 $q$ 行中，每行描述一个按顺序进行的操作，包含 $3$ 或 $4$ 个整数。 - 如果第 $i$ 行包含 $4$ 个整数 $0$、$x_i$、$c_i$ 和 $d_i$（$1 \le x_i \le n$，$1 \le c_i \le q$，$1 \le d \le 10^9$），则第 $i$ 个操作将向树中添加一个颜色为 $c_i$ 的新顶点 $(n + 1)$，并将其与顶点 $x_i$ 连接，边的长度为 $d_i$。 - 如果第 $i$ 行包含 $3$ 个整数 $1$、$x_i$ 和 $c_i$（$1 \le x_i \le n$，$1 \le c_i \le q$），则第 $i$ 个操作将顶点 $x_i$ 的颜色更改为 $c_i$。 保证所有测试用例中 $q$ 的总和不超过 $5 \times 10^5$。 **【输出格式】** 对于每个操作，输出两个不同颜色顶点之间的最大距离。如果不存在有效的顶点对，则输出 $0$。 翻译来自于：[ChatGPT](https://chatgpt.com/)

Your task is to maintain a colorful tree and process queries. At the beginning, there is only one vertex numbered $1$ with color $C$ on the tree. Then there are $q$ operations of two types coming in order: - $0$ $x$ $c$ $d$: Add a new vertex indexed $(n+1)$ with color $c$ to the tree, where $n$ is the current number of existing vertices. An edge connecting vertex $x$ and $(n+1)$ with length $d$ will also be added to the tree. - $1$ $x$ $c$: Change the color of vertex $x$ to $c$. After each operation, you should find a pair of vertices $u$ and $v$ ($1 \le u, v \le n$) with $\textbf{different}$ colors in the current tree so that the distance between $u$ and $v$ is as large as possible. The distance between two vertices $u$ and $v$ is the length of the shortest path from $u$ to $v$ on the tree.

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case: The first line of the input contains two integers $q$ and $C$ ($1 \le q \le 5 \times 10^5$, $1 \le C \le q$) indicating the number of operations and the initial color of vertex $1$. For the following $q$ lines, each line describes an operation taking place in order with $3$ or $4$ integers. - If the $i$-th line contains $4$ integers $0$, $x_i$, $c_i$ and $d_i$ ($1 \le x_i \le n$, $1 \le c_i \le q$, $1 \le d \le 10^9$), the $i$-th operation will add a new vertex $(n + 1)$ with color $c_i$ to the tree and connect it to vertex $x_i$ with an edge of length $d_i$. - If the $i$-th line contains $3$ integers $1$, $x_i$ and $c_i$ ($1 \le x_i \le n$, $1 \le c_i \le q$), the $i$-th operation will change the color of vertex $x_i$ to $c_i$. It's guaranteed that the sum of $q$ of all test cases will not exceed $5 \times 10^5$.

For each operation output the maximum distance between two vertices with different colors. If no valid pair exists output $0$ instead.

2
1 1
0 1 1 1
5 1
0 1 1 1
0 1 2 1
0 3 3 1
1 4 1
1 3 1

0
0
2
3
2
0