#P19010. 【CodeChef START263A】Consistentree (Updates)

【CodeChef START263A】Consistentree (Updates)

题目描述

给定一棵包含 NN 个顶点的树,顶点编号为 11 到 NN。顶点 vv 的权值 AvA_v 为 −1-1、00 或 11。

如果能够将 11 到 NN 这 NN 个不同的整数分别作为各顶点的标签,使每个顶点 vv 都满足对应的条件,就称这棵树为一致的。

  • Av=−1A_v=-1 时,vv 的标签小于它的每个相邻顶点的标签。
  • Av=1A_v=1 时,vv 的标签大于它的每个相邻顶点的标签。
  • Av=0A_v=0 时,vv 至少有一个相邻顶点的标签比它小,并且至少有一个相邻顶点的标签比它大。

接下来依次进行 QQ 次修改。每次选中一个当前权值不为 00 的顶点 vv,将 AvA_v 改为 −Av-A_v。修改会保留,后续修改在当前权值的基础上继续进行。

每次修改后,判断这棵树是否一致。

输入格式

第一行包含一个整数 TT,表示测试用例数。

对于每组测试用例,第一行包含两个以空格分隔的整数 N,QN,Q,分别表示顶点数和修改次数。第二行包含 NN 个以空格分隔的整数 A1,A2,…,ANA_1,A_2,\ldots,A_N,表示初始权值。

接下来的 N−1N-1 行,每行包含两个以空格分隔的整数 u,vu,v,表示顶点 uu 与 vv 之间有一条边。

最后 QQ 行按顺序给出修改,每行包含一个整数 vv,表示此次选中的顶点。

输出格式

每次修改输出一行。若修改后的树一致,输出 YES,否则输出 NO。输出的各字母不区分大小写。

数据范围

  • 1≤T≤1051\le T\le 10^5。
  • 3≤N≤2⋅1053\le N\le 2\cdot 10^5。
  • 1≤Q≤2⋅1051\le Q\le 2\cdot 10^5。
  • Ai∈{−1,0,1}A_i\in\{-1,0,1\},且初始时至少有一个顶点的权值不为 00。
  • 1≤u,v≤N1\le u,v\le N,给出的边构成一棵树。
  • 每次选中的顶点在修改前的权值不为 00。
  • 所有测试用例的 NN 之和不超过 2⋅1052\cdot 10^5,QQ 之和也不超过 2⋅1052\cdot 10^5。

样例输入

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

样例说明

第一组中,第一次修改后的权值为 [−1,−1,1,1,0,1][-1,-1,1,1,0,1],按顶点编号分配标签 [1,2,4,5,3,6][1,2,4,5,3,6] 即可。第二次修改后,顶点 11 和 33 都具有权值 11 且互为邻居。两者都要求标签比对方大,无法满足。

第三组中,第一次修改后,顶点 22 的两个相邻顶点 44、55 的权值都为 11。顶点 22 的标签必须比这两个顶点的标签都小,因而与自身权值 00 对应的条件冲突。第三次修改后,可以按顶点编号分配标签 [2,3,4,5,1][2,3,4,5,1]。

CodeChef 原题 Consistentree (Updates)