Problem:


H - Bit Operation Game

N 頂点の根付き木が与えられる。
頂点には 0 から N &minus; 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 の値が与えられるので、二人が最適な選択をした時の各ゲームのスコアを出力せよ。

Constraints

1  ≤  N  ≤  100000

1  ≤  M  ≤  100000

0  ≤  X, Y 

Input Format

入力は以下の形式で標準入力から与えられる。

N M
o_1
o_2
...
o_{N&minus;1}
u_1 v_1
u_2 v_2
...
u_{N&minus;1} v_{N&minus;1}
X_1 Y_1
X_2 Y_2
...
X_M Y_M

1 行目には木の頂点数 N と、行われるゲーム数を表す整数 M が入力される。 

2 行目から N 行目にかけて、1 ... N&minus;1 番目の頂点に書かれている操作が入力される。

さらに続けて N&minus;1 行に、各辺により繋がれる 2 頂点の番号が入力される。

最後に M 回のゲームにおける X, Y の値が M 行に渡り入力される。

Output Format

各ゲームでの最終的な T の値をそれぞれ M 行に出力せよ。

Sample Input 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

Sample Output 1

4
6
0

 

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 から変化しません



Sample input:
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


Sample output:
4
6
0

Submission status: Accepted

Solution code:
from collections import deque
from itertools import permutations
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    N, M = map(int, readline().split())
    OP = [0]*N
    ops = ["T=T&X\n", "T=T&Y\n", "T=T|X\n", "T=T|Y\n", "T=T^X\n", "T=T^Y\n"]
    for i in range(N-1):
        s = readline()
        OP[i+1] = ops.index(s)
    G = [[] for i in range(N)]
    for i in range(N-1):
        u, v = map(int, readline().split())
        G[u].append(v)
        G[v].append(u)
    used = [0]*N
    used[0] = 1
    P = [-1]*N
    V = []
    D = [0]*N
    que = deque([0])
    for i in range(N):
        v = que.popleft()
        d = D[v]+1
        for w in G[v]:
            if used[w]:
                continue
            used[w] = 1
            que.append(w)
            P[w] = v
            D[w] = d
            V.append(w)
    def check(x, y):
        S = [0]*N
        for v in V:
            op = OP[v]
            s = S[P[v]]
            if op & 1:
                if op & 2:
                    s |= y
                elif op & 4:
                    s ^= y
                else:
                    s &= y
            else:
                if op & 2:
                    s |= x
                elif op & 4:
                    s ^= x
                else:
                    s &= x
            S[v] = s
        T = [-1]*N
        for v in reversed(V):
            if T[v] == -1:
                T[v] = S[v]
            p = P[v]
            if D[v] & 1:
                T[p] = max(T[p], T[v]) if T[p] != -1 else T[v]
            else:
                T[p] = min(T[p], T[v]) if T[p] != -1 else T[v]
        return T[0]

    Q = [(1, 1), (1, 0), (0, 1)]
    R = {}
    for (x0, y0), (x1, y1), (x2, y2) in permutations(Q):
        x = x0 + x1*2 + x2*4
        y = y0 + y1*2 + y2*4
        d = check(x, y)
        d0 = d & 1; d1 = +((d & 2) > 0); d2 = +((d & 4) > 0)
        R[(x0, x1, x2), (y0, y1, y2)] = (d0, d1, d2)
        R[(x1, x2), (y1, y2)] = (d1, d2)
        R[(x2,), (y2,)] = (d2,)
    for i in range(M):
        x, y = map(int, readline().split())
        c = 0
        E = {}
        Q = []
        x0 = x; y0 = y
        while x0 or y0:
            x1 = x0 & 1; y1 = y0 & 1
            if x1 or y1:
                E[x1, y1] = c
            Q.append((x1, y1))
            x0 >>= 1; y0 >>= 1
            c += 1
        if not E:
            write("0\n")
            continue
        *S, = E.keys()
        S.sort(key = E.__getitem__)
        x1 = tuple(p for p, q in S)
        y1 = tuple(q for p, q in S)
        d1 = R[x1, y1]
        for p, q, d in zip(x1, y1, d1):
            E[p, q] = d
        Q.reverse()
        ans = 0
        for p, q in Q:
            if p or q:
                ans = (ans << 1) | E[p, q]
            else:
                ans <<= 1
        write("%d\n" % ans)
solve()