問題一覧 > 通常問題

No.363 門松サイクル

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

問題文

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

  • A1,A2,A3 は全て異なる
  • 3 つの要素の中で A2 が最も大きい、または、A2 が最も小さい

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

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


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

入力

N
A1 A2  AN
x1 y1
x2 y2

xN1 yN1
Q
u1 v1
u2 v2

uQ vQ

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

入力は全て整数で、以下の制約を満たします。
2N105
1Ai105
1xi,yiN
xiyi
木に多重辺や自己ループはなく、連結であることが保証されます。

1Q105
1ui,viN
uivi

入出力の数が多いので出来るだけ高速な入出力を使うことをお勧めします。 実行時間制限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もしくは右上の雲マークをクリックしてアカウントを作成してください。