#P19010. 【CodeChef START263A】Consistentree (Updates)
【CodeChef START263A】Consistentree (Updates)
题目描述
给定一棵包含 个顶点的树,顶点编号为 到 。顶点 的权值 为 、 或 。
如果能够将 到 这 个不同的整数分别作为各顶点的标签,使每个顶点 都满足对应的条件,就称这棵树为一致的。
- 时, 的标签小于它的每个相邻顶点的标签。
- 时, 的标签大于它的每个相邻顶点的标签。
- 时, 至少有一个相邻顶点的标签比它小,并且至少有一个相邻顶点的标签比它大。
接下来依次进行 次修改。每次选中一个当前权值不为 的顶点 ,将 改为 。修改会保留,后续修改在当前权值的基础上继续进行。
每次修改后,判断这棵树是否一致。
输入格式
第一行包含一个整数 ,表示测试用例数。
对于每组测试用例,第一行包含两个以空格分隔的整数 ,分别表示顶点数和修改次数。第二行包含 个以空格分隔的整数 ,表示初始权值。
接下来的 行,每行包含两个以空格分隔的整数 ,表示顶点 与 之间有一条边。
最后 行按顺序给出修改,每行包含一个整数 ,表示此次选中的顶点。
输出格式
每次修改输出一行。若修改后的树一致,输出 YES,否则输出 NO。输出的各字母不区分大小写。
数据范围
- 。
- 。
- 。
- ,且初始时至少有一个顶点的权值不为 。
- ,给出的边构成一棵树。
- 每次选中的顶点在修改前的权值不为 。
- 所有测试用例的 之和不超过 , 之和也不超过 。
样例输入
4
6 6
-1 -1 -1 1 0 1
5 6
2 4
3 1
5 2
3 5
3
1
3
4
2
6
6 6
1 0 -1 1 0 -1
2 6
5 1
2 5
5 4
2 3
1
4
6
3
1
4
5 6
0 0 -1 -1 1
4 2
2 5
5 1
1 3
4
5
3
4
5
3
7 6
1 0 1 -1 -1 0 -1
2 5
6 1
5 3
6 7
3 6
2 4
4
7
1
4
7
4
样例输出
YES
NO
YES
NO
YES
YES
YES
NO
YES
YES
YES
NO
NO
NO
YES
NO
NO
YES
YES
NO
YES
NO
NO
YES
样例说明
第一组中,第一次修改后的权值为 ,按顶点编号分配标签 即可。第二次修改后,顶点 和 都具有权值 且互为邻居。两者都要求标签比对方大,无法满足。
第三组中,第一次修改后,顶点 的两个相邻顶点 、 的权值都为 。顶点 的标签必须比这两个顶点的标签都小,因而与自身权值 对应的条件冲突。第三次修改后,可以按顶点编号分配标签 。
相关
在下列比赛中: