配点 : 100 点
問題文
N 顶点树 给出了 T 。侧面 i 是顶点 u_i 和 在 v_i 是平局。 第一、顶点 i 是一种颜色 它涂有 A_i 。 您将收到 Q 查询,因此请按顺序处理它们。查询如下 2 其中一种。
1 k x: 頂点 k 颜色 用 x 绘画 涂有2 y: 色 y 画有 2 输出顶点的最大距离
在这里,2 頂点 (u,v) 的距离是 以u 和 在 v 作为两个端点的路径中包含的边数。
制約
- 2 \le N \le 10^5
- 1 \le u_i,v_i \le N
- 1 \le A_i \le N
- 1 \le Q \le 10^5
- 1 \le k \le N
- 1 \le x \le N
- 1 \le y \le N
- 查询
当给出
2 y时,颜色 用 y 绘制的顶点 2 存在多个 - 所有输入均为整数
- 给定的图是一棵树
入力
输入是按以下格式从标准输入给出的。
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
出力
第二种形式的查询次数为 请输出 q 作为 q 行。 行 j (1\leq j \leq q) 在行 2 表单的查询 j 打印该项目的答案。
入力例 1
3 1 2 2 3 1 1 1 3 2 1 1 1 2 2 1
出力例 1
2 1
首先,所有方块都是彩色的 它涂有 1 。这时,颜色 1 画有 2 顶点之中,顶点 1 和边 3 为最大距离,距离为 2 。 然后是顶点 1 是颜色 当用 2 绘制时,颜色 对于用 1 绘制的顶点,顶点 距离为 2 和边 3 是距离 1 是最大值。
入力例 2
4 1 2 1 3 1 4 1 1 2 2 5 2 1 2 2 1 1 3 1 3 3 2 3
出力例 2
1 2 1
入力例 3
6 1 2 2 3 3 4 4 5 4 6 1 3 2 1 1 3 6 2 1 1 2 3 1 1 2 1 6 4 2 1 2 2
出力例 3
4 1 2