問題一覧 > 通常問題

No.363 門松サイクル

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 27
作問者 : koyumeishikoyumeishi / テスター : uwiuwi
2 ProblemId : 1024 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2016-05-24 14:32:19

問題文

門松列 とは $3$ 個の要素からなる数列 $A_1, A_2, A_3$ で以下 2 つの条件を満たすものです。

  • $A_1, A_2, A_3$ は全て異なる
  • $3$ つの要素の中で $A_2$ が最も大きい、または、$A_2$ が最も小さい

頂点$i$が値$Ai$をもつグラフの閉路が以下 2 つの条件を満たすとき、この閉路を門松サイクルといいます。

  • 閉路の頂点数が3以上
  • 閉路上の連続する3頂点を$u,v,w$としたとき、全ての $u,v,w$ について、数列 $A_u,A_v,A_w$ が門松列である
下図のグラフでは、左上の閉路だけが門松サイクルです。


頂点$i$が値$Ai$をもつ$N$頂点の木があります。
この木に新たに 頂点$u$ と 頂点$v$ ($u \neq v$) を結ぶ辺を追加すると、ちょうど一つの閉路ができます。
こうして出来た閉路は門松サイクルになるでしょうか。 $Q$個の辺についてそれぞれ答えてください。
門松サイクルであるとき "YES"、そうでないときは "NO" と、1行ずつ出力してください。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_{N-1}$ $y_{N-1}$
$Q$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_Q$ $v_Q$

1行目に木の頂点数$N$が与えられます。
2行目に頂点$i$ の持つ値$A_i$が空白区切りで与えられます。
3行目以降$N-1$行に、辺の情報が与えられます。 $i$番目の辺は頂点$x_i$と頂点$y_i$を結ぶ辺です。
3+N-1行目に新たに追加される辺の数$Q$が与えれます。
3+N行目以降$Q$行に、新たに追加される辺の情報が与えられます。 $i$番目の辺は頂点$u_i$と頂点$v_i$を結ぶ辺です。
$Q$個の辺はそれぞれ独立に木に追加されるものとします。$i$番目に追加された辺は、$j$番目($i \neq j$)のグラフには影響しません。

入力は全て整数で、以下の制約を満たします。
$2 \leq N \leq 10^5$
$1 \leq A_i \leq 10^5$
$1 \leq x_i,y_i \leq N$
$x_i \neq y_i$
木に多重辺や自己ループはなく、連結であることが保証されます。

$1 \leq Q \leq 10^5$
$1 \leq u_i, v_i \leq N$
$u_i \neq v_i$

入出力の数が多いので出来るだけ高速な入出力を使うことをお勧めします。 実行時間制限4秒のうちの2秒分は入出力用だと思って設定しています。

出力

木に新たに辺を追加して出来た閉路が門松サイクルであるとき "YES"、そうでないときは "NO" を、各辺について1行ずつ出力してください。

サンプル

サンプル1
入力
7
1 5 4 6 3 4 3
1 2
2 3
3 4
2 5
1 6
6 7
4
4 5
4 7
5 7
3 5
出力
YES
YES
NO
NO


下図はこの木に辺を追加したものです。 辺はそれぞれ独立に追加されることに注意して下さい。

サンプル2
入力
7
1 5 4 6 3 4 3
1 2
2 3
3 4
4 5
5 6
6 7
5
1 2
1 5
3 7
6 1
1 4
出力
NO
NO
NO
YES
YES

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