No.2822 Lights Up! (Tree Edition)
タグ : / 解いたユーザー数 37
作問者 :
みどりむし🦠
/ テスター :
FplusFplusF
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もしくは右上の雲マークをクリックしてアカウントを作成してください。