P9665 [ICPC 2021 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$ 的最短路径的长度。

无

无