31692번 - Colourful Tree 다국어

문제

Your task is to maintain a colourful tree and process queries.

At the beginning, there is only one vertex numbered 1ドル$ with colour $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 colour $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 colour of vertex $x$ to $c$.

After each operation, you should find a pair of vertices $u$ and $v$ (1ドル ≤ u, v ≤ n$) with different colours 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ドル ≤ q ≤ 5 \times 10^5,ドル 1ドル ≤ C ≤ q$) indicating the number of operations and the initial colour 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ドル ≤ x_i ≤ n,ドル 1ドル ≤ c_i ≤ q,ドル 1ドル ≤ d ≤ 10^9$), the $i$-th operation will add a new vertex $(n + 1)$ with colour $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ドル ≤ x_i ≤ n,ドル 1ドル ≤ c_i ≤ q$), the $i$-th operation will change the colour 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 colours. If no valid pair exists output 0ドル$ instead.

제한

힌트