AT_nupc2024_f Labeled Tree Distance

给定一棵有 $N$ 个顶点的树 $T$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。最开始时，顶点 $i$ 被涂成颜色 $A_i$。接下来给出 $Q$ 个操作，请依次处理每个操作。操作有以下两种类型之一： - `1 k x`：将顶点 $k$ 涂成颜色 $x$。 - `2 y`：输出被颜色 $y$ 涂色的任意两个顶点之间的距离的最大值。 这里，两个顶点 $(u, v)$ 的距离指的是以 $u$ 和 $v$ 为端点的路径上包含的边的数量。

输入以如下格式从标准输入读入。 > $N$ > $u_1$ $v_1$ > $u_2$ $v_2$ > $\vdots$ > $u_{N-1}$ $v_{N-1}$ > $A_1\ A_2\ \ldots\ A_N$ > $Q$ > $\mathrm{query}_1$ > $\mathrm{query}_2$ > $\vdots$ > $\mathrm{query}_Q$ 其中，$\mathrm{query}_i$ 表示第 $i$ 个查询，格式如下之一： > $1\ k\ x$ > $2\ y$

设第 2 类查询的次数为 $q$，请输出 $q$ 行。对于第 $j\ (1 \le j \le q)$ 行，输出对应于第 $j$ 个第 2 类查询的结果。

### 样例解释 1 最初所有节点都被颜色 $1$ 覆盖，此时颜色 $1$ 覆盖的两个顶点中距离最大的为顶点 $1$ 与顶点 $3$，其距离为 $2$。之后，如果将顶点 $1$ 改涂为颜色 $2$，则此时颜色 $1$ 覆盖的顶点为顶点 $2$ 和顶点 $3$，它们之间的距离为 $1$。 ### 数据范围 - $2 \leq N \leq 10^5$ - $1 \leq u_i,v_i \leq N$ - $1 \leq A_i \leq N$ - $1 \leq Q \leq 10^5$ - $1 \leq k \leq N$ - $1 \leq x \leq N$ - $1 \leq y \leq N$ - 对于任意一个查询 `2 y`，颜色 $y$ 至少会覆盖 2 个顶点。 - 输入均为整数。 - 输入的图一定是一棵树。 由 ChatGPT 5 翻译