(13:43:00) 修复了示例输入 1 的图表
输入是按以下格式从标准输入给出的。
每场比赛的决赛 T 的每个值 M 行输出。
由于字符串以
(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 开始变化。
问题陈述
N 给出了一个有根的顶点树。
在顶部
它的编号为 0 假设一直下雨,直到 N-1 。
第0个顶点代表根。
在根部 T = 0 但对于其他顶点
T=T&XT=T&YT=T|XT=T|YT=T^XT=T^Y
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 多行输入。
输出格式
示例输入 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 开始变化。