#P18363. Perfect Suika Game on a Tree
Perfect Suika Game on a Tree
Perfect Suika Game on a Tree
题目描述
给定一棵有 个顶点的树 ,顶点编号为 。第 条边连接 和 。
每个顶点都有一个称为等级的正整数。初始时,顶点 的等级为 。
对于这棵树,考虑以下判定问题:能否恰好执行 次下述操作,把树变成只有一个顶点的树?
- 选择一条两个端点等级相同的边,将这条边缩约。如果两个端点的共同等级为 ,则缩约得到的新顶点等级为 。
现在需要处理 次询问。第 次询问给出一个边编号 :交换原树中顶点 和 的等级,然后回答上述判定问题。
交换对后续询问也生效。每次询问中的缩约只是用来判断能否成功,不会实际改变后续询问所使用的原树。
输入格式
第一行一个整数 。
接下来 行,第 行两个整数 ,表示编号为 的边。
接下来一行 个整数 。
接下来一行一个整数 。
接下来 行,第 行一个整数 ,表示本次交换的边编号。
输出格式
输出 行。
第 行对应第 次交换之后的状态。如果能够通过上述操作把树缩约为一个顶点,输出 Yes,否则输出 No。
数据范围
- 所有输入均为整数。
- 。
- ,输入图是一棵树。
- 。
- 。
- 。
- 每个输入文件只有一组数据。
样例输入 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 的顶点合成等级 2,再与原有的等级 2 顶点合成等级 3,最后合成等级 4,因此输出 Yes。

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