#yukicoder 2822 Lights Up(Tree Edition) #offline LCA O(Nα(N) + Q) def offline_LCA(N, G, parent_v, Query): ans = [-1] * len(Query); Tasks = [[] for _ in range(N)]; *UF, = range(N); visit = []; T = [(parent_v, -1)] for q,(u,v) in enumerate(Query): if u == v: ans[q] = u else: Tasks[u].append((v,q)); Tasks[v].append((u,q)) def find(v): vertices = [] while UF[v] != v: vertices.append(v); v = UF[v] for i in vertices: UF[i] = v return v def unite(x,y): x,y = find(x), find(y) if x < y: UF[y] = x; return x else: UF[x] = y; return y while T: #pre-order counting now,back = T.pop(); visit.append(now) for next in G[now]: T.append((next,now)) if next != back else None R = {v:t for t,v in enumerate(visit)}; T = [(parent_v, -1)] while T: #LCA calculate now,back = T.pop() if now >= 0: #入りがけの処理 T.append((~now,back)); now_time = R[now] for next in G[now]: T.append((next,now)) if next != back else None for v,q in Tasks[now]: pair_time = R[v] if pair_time <= now_time: ans[q] = visit[find(pair_time)] else: p = R[~now]; unite(p, p-1) #帰りがけ処理。祖先情報を消す return ans #入力受取 N = int(input()) P = [-1] + list(map(lambda x: int(x) - 1, input().split())) S = [0] + [0 if Si == '.' else 1 for Si in input()] K = int(input()) T = [tuple(map(lambda x: int(x) - 1, input().split())) for _ in range(K)] #えーごめんなさい LCAはライブラリで甘えます・・・ nG = [[] for _ in range(N)] for now, Pi in enumerate(P[1:], start = 1): nG[now].append(Pi) nG[Pi].append(now) L = offline_LCA(N, nG, 0, T) #ETを用意 #visited[i][f]: 頂点iに(入りがけ / 出がけ)の時刻 visited = [[None] * 2 for _ in range(N)] arrival = [None] * 2 * N stack = [0] for t in range(2 * N): now = stack.pop() if now >= 0: #入りがけの処理 visited[now][0] = t stack.append(~now) arrival[t] = now for nxt in nG[now]: if visited[nxt][0] == None: stack.append(nxt) else: #帰りがけの処理 now = ~now visited[now][1] = t arrival[t] = now #辺の色の情報を配列Cに記録 辺は子の入りがけ番号に対応させる C = [0] * 2 * N for now, Pi in enumerate(P[1:], start = 1): t = visited[now][0] assert C[t] == 0 if S[now] == 1: C[t] = 1 #Cの差分列をとり、これをEとする E = [C[0]] + [abs(C[i] - C[i + 1]) for i in range(2 * N - 1)] + [C[-1]] #u - vパスを考える(ET訪問順はu < vとしてよい)。 #半開区間 (u入りがけ: v入りがけ] に該当する辺をxorにかければよい #[u_in + 1: v_in + 1)が反転するわけで、xorの差分を考えるとE[Lt], E[Rt] がxor反転する #あとは同じ辺同士も反転子を持つ必要がある これは後で処理 G = [[] for _ in range(2 * N + 1)] for Ui, Vi in T: Uv, Vv = visited[Ui][0], visited[Vi][0] if Uv > Vv: Uv, Vv = Vv, Uv G[Uv + 1].append(Vv + 1) G[Vv + 1].append(Uv + 1) #入りがけの時刻と出がけの時刻を同時に反転させてもよい for i in range(1, N): G[ visited[i][0] ].append( visited[i][1] + 1 ) G[ visited[i][1] + 1 ].append( visited[i][0] ) #後はDFS木を取って葉から貪欲 used = [False] * (2 * N + 1) for p in range(2 * N + 1): if used[p] == True: continue used[p] = True stack = [(p, -1)] for now, back in stack: assert used[now] == True for nxt in G[now]: if used[nxt] == False: used[nxt] = True stack.append((nxt, now)) while stack: now, back = stack.pop() for nxt in G[now]: if nxt != back and E[nxt] == 1: E[now], E[nxt] = E[now] ^ 1, E[nxt] ^ 1 #答えを出力 assert all(used) print('Yes' if not any(E) else 'No')