AT_icpc2015summer_day2_h Bit Operation Game

输入数据通过标准输入以如下格式给出： > $ N $ $ M $ $ o_1 $ $ o_2 $ $ \ldots $ $ o_{N-1} $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \ldots $ $ u_{N-1} $ $ v_{N-1} $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \ldots $ $ X_M $ $ Y_M $ 第一行给出两个整数，分别是树的顶点数量 $ N $ 和进行游戏的次数 $ M $。 接下来的 $ N-1 $ 行中，每行描述了编号从 $ 1 $ 到 $ N-1 $ 的顶点上写的操作。 然后是 $ N-1 $ 行，每行给出了由一条边连接的两个顶点编号。 最后 $ M $ 行，每行表示一次游戏中的 $ X $ 和 $ Y $ 的值。 请根据输入打印出每次游戏最终的 $ T $ 值。 示例： ``` 输入： 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 输出： 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 \oplus 5 = 6 $。 - 当 $ X = 0 $, $ Y = 0 $ 时，无论选择哪个路径，$ T $ 都保持为 0。 ### 数据范围与提示 在这个问题中，我们有一个由 $ 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` 这里的运算符 &、|、^ 分别为按位与、按位或和按位异或。两位玩家 A 君和 B 君将进行 $ M $ 次游戏。游戏开始时，两人在根节点出发，交替选择子节点前进直至到达叶子节点。途经的节点操作依次应用，最终得到的 $ T $ 值即为此次游戏的分数。B 君希望分数尽可能小，而 A 君则希望尽可能大。给定每次游戏的 $ X $ 和 $ Y $，请输出两人在最优策略下的每局游戏分数。 - $ 1 \leq N \leq 100000 $ - $ 1 \leq M \leq 100000 $ - $ 0 \leq X, Y $ **本翻译由 AI 自动生成**

无

无

### Constraints $ 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 $