← 返回题目列表

AtCoder · nupc2024_f

F. 标记树距离

中文机器翻译题面 查看原题

配点 : 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