#P18314. Tree Flip
Tree Flip
Tree Flip
题目描述
Alu 得到一棵有根树,每个节点的值为 或 。他可以选择一个节点进行一次翻转:将该节点和它的所有直接孩子的值分别取反,即 变成 、 变成 。一次操作只影响所选节点及其直接孩子,不影响更深的后代。
Alu 会使用尽可能少的操作,使所有节点的值都变成 。
Begun 持有这棵树,并依次进行两类更新:
1 x:只将节点 自身的值取反,孩子的值不变。2 x:将节点 设为整棵树的新根,所有节点的值不变。
初始时,节点 是树根。每次更新后,输出在当前点值和当前根的条件下,Alu 将整棵树清零所需的最少操作次数。
Alu 的操作只是在树的一个副本上进行。求答案时假想执行的清零操作,不会改变 Begun 实际维护的树,也不会影响后续更新。
输入格式
第一行包含整数 ,表示测试用例数。
每个测试用例:
- 第一行包含正整数 ,分别表示节点数和更新次数。
- 第二行包含 个整数 ,其中 。
- 接下来 行,每行包含两个整数 ,表示一条无向边。
- 接下来 行,每行包含两个整数 ,表示一次上述更新。
保证输入边构成一棵合法的树,节点编号为 。
输出格式
按照输入顺序处理所有测试用例。每次更新后,单独输出一行,表示 Alu 所需的最少操作次数。
数据范围
- ;
- 为正整数;
- ;
- ,;
- 所有测试用例的 之和不超过 ;
- 所有测试用例的 之和不超过 。
因此,每个测试用例也有 。
样例
输入
1
3 3
0 0 1
1 2
3 1
1 1
2 2
1 1
输出
2
1
1
说明
原题示例图如下。圆括号中的数是节点的值,箭头由父节点指向孩子。图中依次说明初始树及三次更新后的情况。

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