#P18363. Perfect Suika Game on a Tree

Perfect Suika Game on a Tree

Perfect Suika Game on a Tree

题目描述

给定一棵有 NN 个顶点的树 TT,顶点编号为 1,2,…,N1,2,\ldots,N。第 ii 条边连接 uiu_i 和 viv_i。

每个顶点都有一个称为等级的正整数。初始时,顶点 vv 的等级为 AvA_v。

对于这棵树,考虑以下判定问题:能否恰好执行 N−1N-1 次下述操作,把树变成只有一个顶点的树?

  • 选择一条两个端点等级相同的边,将这条边缩约。如果两个端点的共同等级为 ll,则缩约得到的新顶点等级为 l+1l+1。

现在需要处理 QQ 次询问。第 ii 次询问给出一个边编号 eie_i:交换原树中顶点 ueiu_{e_i} 和 veiv_{e_i} 的等级,然后回答上述判定问题。

交换对后续询问也生效。每次询问中的缩约只是用来判断能否成功,不会实际改变后续询问所使用的原树。

输入格式

第一行一个整数 NN。

接下来 N−1N-1 行,第 ii 行两个整数 ui,viu_i,v_i,表示编号为 ii 的边。

接下来一行 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

接下来一行一个整数 QQ。

接下来 QQ 行,第 ii 行一个整数 eie_i,表示本次交换的边编号。

输出格式

输出 QQ 行。

第 ii 行对应第 ii 次交换之后的状态。如果能够通过上述操作把树缩约为一个顶点,输出 Yes,否则输出 No。

数据范围

  • 所有输入均为整数。
  • 2≤N≤2×1052\le N\le2\times10^5。
  • 1≤ui,vi≤N1\le u_i,v_i\le N,输入图是一棵树。
  • 1≤Ai≤N1\le A_i\le N。
  • 1≤Q≤2×1051\le Q\le2\times10^5。
  • 1≤ei≤N−11\le e_i\le N-1。
  • 每个输入文件只有一组数据。

样例输入 1

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

样例输出 1

Yes
No
No
Yes

样例输入 2

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

样例输出 2

No
No
No
No
Yes
No
No
No
Yes
No

样例解释

样例 1 的第一次询问交换边 1 的两个端点,等级仍为 (1,1,2,3)(1,1,2,3)。可以依次把两个等级 1 的顶点合成等级 2,再与原有的等级 2 顶点合成等级 3,最后合成等级 4,因此输出 Yes。

样例1第一次询问的缩约过程

第二次询问之后,等级变成 (2,1,1,3)(2,1,1,3)。这时不存在两个端点等级相同的边,无法执行任何操作,因此输出 No。