No.2822 Lights Up! (Tree Edition)
タグ : / 解いたユーザー数 36
作問者 :
![🦠みどりむし](https://pbs.twimg.com/profile_images/1258989583968043008/WWF0Yz3c.jpg)
![FplusFplusF](https://pbs.twimg.com/profile_images/1535630966743371776/RVkOr4C0.jpg)
![AngrySadEight](https://pbs.twimg.com/profile_images/1774819988135927808/f4w6hc33.jpg)
問題文
$N$ 個の頂点、頂点 $1, 2, \dots, N$ と、$N - 1$ 本の辺、辺 $2, 3, \dots, N$ からならる無向木があります。
辺 $i \scriptsize \; (2 \leq i \leq N)$ は、頂点 $i$ と頂点 $ P_i$ とを結ぶ辺です。またここで $P_i < i$ を満たします。
はじめ、辺 $i \scriptsize \; (2 \leq i \leq N)$ は、$S_i =$ .
のとき白で、$S_i =$ #
のとき黒で塗られています。
ところで、$K$ 個の操作、操作 $1, 2, \dots, K$ があります。
操作 $i \scriptsize \; (1 \leq i \leq K)$ は以下です:
- $2$ 頂点 $U_i, V_i$ を結ぶ最短パスに属するすべての辺それぞれについて、その色を反転する。(黒ならば白で、白ならば黒で塗り直す。)
uni くんは、これらの操作を、自由な順番で、それぞれ何度ずつでも行うことができます。
uni くんの目標は、すべての辺が白で塗られているようにすることです。
この目標を達成することができるかどうかを判定してください。
入力
入力は、以下の形式で標準入力より与えられる:
$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$
出力
目標が達成できるならば Yes
、そうでないならば No
と標準出力へ一行に出力せよ。
制約
- $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)$ は整数
サンプル
入出力例1
入力
5 1 1 3 3 #.## 3 2 4 3 4 1 5
出力
Yes
操作 $1, 3$ をそれぞれ $1$ 度ずつ行うことにより、目標が達成できます。
入出力例2
入力
5 1 2 2 3 #### 3 1 2 3 4 1 4
出力
No
どのように操作を行っても、目標は達成できません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。