← 返回题目列表

AtCoder · icpc2015summer_day2_h

H. 位运算游戏

中文机器翻译题面 查看原题
(13:43:00) 修复了示例输入 1 的图表

问题陈述

N 给出了一个有根的顶点树。 在顶部 它的编号为 0 假设一直下雨,直到 N-1 。 第0个顶点代表根。 在根部 T = 0 但对于其他顶点

  • T=T&X
  • T=T&Y
  • T=T|X
  • T=T|Y
  • T=T^X
  • T=T^Y
写入以下操作之一。 这里的运算符&、|、^分别表示按位运算符and、or、xor。

A 先生和 B 先生使用这棵树玩以下游戏。 我去过那里 M 次。 两者从根开始,选择子顶点,交替进行,从A先生开始,直到到达叶子。 当在传递的节点上写入的操作按照传递的顺序应用时的最终结果。 T 的值成为分数。 B先生想尽可能降低分数,A先生想提高分数。 M 游戏 给定 X, Y 的值,打印双方都做出最优选择时每场比赛的得分。


约束

  • 1 \leq N \leq 100000
  • 1 \leq M \leq 100000
  • 0 \leq X, Y < 2^{16}

输入格式

输入是按以下格式从标准输入给出的。
N M
o_1
o_2
...
o_{N-1}
u_1 v_1
u_2 v_2
...
u_{N-1} v_{N-1}
X_1 Y_1
X_2 Y_2
...
X_M Y_M

1 行中显示树的顶点数 N 和一个代表玩过的游戏数的整数 输入 M 。 朝向
2 从行 N 线, 输入写入第1 ~ N-1 个顶点的操作。
继续 N-1 通过每条边连接到行 2 输入顶点编号。
终于 M 在游戏中 X, Y 的值为 M 多行输入。

输出格式

每场比赛的决赛 T 的每个值 M 行输出。 由于字符串以

示例输入 1

6 3
T=T|X
T=T|Y
T=T|Y
T=T^Y
T=T&X
0 1
0 2
1 3
1 4
2 5
5 6
3 5
0 0

示例输出 1

4
6
0

[原图]


(13:43:00) 修复了图表
如果 X = 5,Y = 6,则转到顶点 0 -> 2 -> 5,导致 T = 5 & 6 = 4
如果 X = 3,Y = 5,则从顶点 0 -> 1 -> 4,得到 T = 3 ^ 5 = 6
如果 X = 0,Y = 0,则无论经过哪里,T 都不会从 0 开始变化。