#P18314. Tree Flip

Tree Flip

Tree Flip

题目描述

Alu 得到一棵有根树,每个节点的值为 00 或 11。他可以选择一个节点进行一次翻转:将该节点和它的所有直接孩子的值分别取反,即 00 变成 11、11 变成 00。一次操作只影响所选节点及其直接孩子,不影响更深的后代。

Alu 会使用尽可能少的操作,使所有节点的值都变成 00。

Begun 持有这棵树,并依次进行两类更新:

  1. 1 x:只将节点 xx 自身的值取反,孩子的值不变。
  2. 2 x:将节点 xx 设为整棵树的新根,所有节点的值不变。

初始时,节点 11 是树根。每次更新后,输出在当前点值和当前根的条件下,Alu 将整棵树清零所需的最少操作次数。

Alu 的操作只是在树的一个副本上进行。求答案时假想执行的清零操作,不会改变 Begun 实际维护的树,也不会影响后续更新。

输入格式

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

每个测试用例:

  • 第一行包含正整数 n,qn,q,分别表示节点数和更新次数。
  • 第二行包含 nn 个整数 a1,…,ana_1,\ldots,a_n,其中 ai∈{0,1}a_i\in\{0,1\}。
  • 接下来 n−1n-1 行,每行包含两个整数 u,vu,v,表示一条无向边。
  • 接下来 qq 行,每行包含两个整数 type,xtype,x,表示一次上述更新。

保证输入边构成一棵合法的树,节点编号为 1,…,n1,\ldots,n。

输出格式

按照输入顺序处理所有测试用例。每次更新后,单独输出一行,表示 Alu 所需的最少操作次数。

数据范围

  • 1≤T≤1041\le T\le 10^4;
  • n,qn,q 为正整数;
  • ai∈{0,1}a_i\in\{0,1\};
  • 1≤u,v,x≤n1\le u,v,x\le n,type∈{1,2}type\in\{1,2\};
  • 所有测试用例的 nn 之和不超过 10510^5;
  • 所有测试用例的 qq 之和不超过 10510^5。

因此,每个测试用例也有 n,q≤105n,q\le 10^5。

样例

输入

1
3 3
0 0 1
1 2
3 1
1 1
2 2
1 1

输出

2
1
1

说明

原题示例图如下。圆括号中的数是节点的值,箭头由父节点指向孩子。图中依次说明初始树及三次更新后的情况。

原题的翻转与换根示例

  • 第一次更新为 1 1:仅翻转节点 11 的值。Alu 可以先对节点 22 操作,再对节点 11 操作,共需 22 次。
  • 第二次更新为 2 2:令节点 22 为根。Alu 只需对节点 11 操作,共需 11 次。
  • 第三次更新为 1 1:再次仅翻转节点 11。Alu 只需对节点 33 操作,共需 11 次。