問題一覧 > 通常問題

No.2822 Lights Up! (Tree Edition)

レベル : / AI推定難易度 : 1850 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 37
作問者 : みどりむし🦠 / テスター : FplusFplusF viral8 achapi 👑 AngrySadEight
お気に入りにしたユーザー ProblemId : 10815 / 自分の提出
問題文最終更新日: 2024-07-26 20:24:56
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 438 (順位表) の他の問題:

Problem Statement

There is an undirected tree consisting of $N$ vertices, vertices $1, 2, \dots, N$, and $N - 1$ edges, edges $2, 3, \dots, N$.
Edge $i \scriptsize \; (2 \leq i \leq N)$ connects vertex $i$ and vertex $ P_i$. Here, $P_i < i$ holds.

Initially, edge $i \scriptsize \; (2 \leq i \leq N)$ is painted white if $S_i =$ ., and black if $S_i =$ #.

There are also $K$ operations, operations $1, 2, \dots, K$.
Operation $i \scriptsize \; (1 \leq i \leq K)$ is as follows:

  • For every edge on the shortest path connecting the $2$ vertices $U_i, V_i$, flip its color. (Repaint it white if it is black, and black if it is white.)

Uni can perform these operations in any order, each of them any number of times.

Uni's goal is to have all edges painted white.
Determine whether this goal can be achieved.

Input

The input is given from standard input in the following format:

$N$
$P_2 \enspace P_3 \enspace \dots \enspace P_N$
$S_2 S_3 \dots S_N$
$K$
$U_1 \enspace V_1$
$U_2 \enspace V_2$
$\vdots$
$U_K \enspace V_K$

Output

Print Yes if the goal can be achieved, and No otherwise, on a single line to standard output.

Constraints

  • $2 \leq N \leq 10^5$
  • $1 \leq K \leq 10^5$
  • $1 \leq P_i < i \scriptsize \; (2 \leq i \leq N)$
  • $1 \leq U_i < V_i \leq N \scriptsize \; (1 \leq i \leq K)$
  • $S_i \in \{$ .$, $ # $\} \scriptsize \; (2 \leq i \leq N)$
  • $N, K, P_i, U_j, V_j \scriptsize \; (2 \leq i \leq N) \; (1 \leq j \leq K)$ are integers.

Sample

Sample Input/Output 1
Input
5
1 1 3 3
#.##
3
2 4
3 4
1 5
Output
Yes

The goal can be achieved by performing each of operations $1, 3$ exactly $1$ time.

Sample Input/Output 2
Input
5
1 2 2 3
####
3
1 2
3 4
1 4
Output
No

No matter how the operations are performed, the goal cannot be achieved.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。