← 返回题目列表

AtCoder · utpc2024_p

P. 树上的完美 Suika 游戏

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

配点 : 100 点

問題文

1 不同编号的点最多为 N 编号最多为 N 顶点树 有 T 。 连接 i 第一条边是顶点 u_i,v_i 。

每个顶点都有等级 它被分配一个称为的正整数。一开始,每个顶点 v = 1,2,\dots,N 的级别是 考虑以下有关 A_v 。

木 T 的问题。 只需对

木 T 进行以下操作即可 通过执行 N-1 次, T 在 1 确定是否可以创建仅由顶点组成的树。
  • 创建一条两端点具有相同顶点级别的边。 1 选择一条边缘并对所选边缘执行缩小操作。两个端点的顶点的水平 l ,缩减生成的新顶点的级别为 l+1 。

查询是 您将获得 Q 碎片,请处理它们。 在第 i 次查询中,边数 给出了 e_i ,所以树 T 中的顶点 交换 u_{e_i},v_{e_i} 的级别后(此交换的影响保留在后续查询中),打印上述问题的答案。

制約

  • 输入都是整数
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq u_i,v_i \leq N
  • 1 \leq A_i \leq N
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq e_i \leq N-1
  • 给定的图是一棵树

部分点

  • 附加限制 如果正确答案是满足 Q=1 的数据集 20 点。

请注意,下面给出的示例案例均不包含在部分点数据集中。 对于上述问题,在对第


入力

输入是按以下格式从标准输入给出的。

N 
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
A_1 A_2 \dots A_N
Q
e_1
e_2
\vdots
e_Q

出力

Q 行。 打印第 i 在线 i 个查询进行级别交换后,T 在 1 当可以制作仅由顶点组成的树时 如果您不能 Yes 对于第 No 。


入力例 1

4
1 2
1 3
1 4
1 1 2 3
4
1
2
3
1

出力例 1

Yes
No
No
Yes

1 个查询,顶点 交换 u_1=1, v_1=2 的级别后,顶点 1,2,3,4 的每个级别 1,1,2,3 。

在这种情况下,通过选择如下所示的红色显示的一侧并执行操作,可以将其升级。 4 的顶点 1 (下图中,顶点处写的整数表示该顶点的级别)。

縮約操作の例

因此 1 在线 Yes 。

2 个查询,顶点 交换 u_2=1, v_2=3 的级别后,顶点 1,2,3,4 的每个级别 2,1,1,3 。

在这种情况下,操作 1 我什至做不到, 1 无法转换为只有一个顶点的树。

因此 2 在线 No 。


入力例 2

15
1 2
1 3
2 4
1 5
1 6
4 7
1 8
7 9
2 10
2 11
2 12
11 13
11 14
2 15
2 3 13 4 8 10 7 9 11 12 1 1 6 14 5
1
11

出力例 2

Yes

入力例 3

20
1 2
1 3
2 4
1 5
2 6
5 7
4 8
3 9
6 10
7 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
4 4 7 3 8 2 8 6 4 2 3 3 4 5 6 5 4 3 3 6
10
8
19
5
9
19
10
19
19
10
19

出力例 3

No
No
No
No
Yes
No
No
No
Yes
No