問題一覧 > 通常問題

No.1719 Tree and Permutation

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 21
作問者 : nok0nok0 / テスター : zkouzkou Kite_kumaKite_kuma 👑 ygussanyygussany
5 ProblemId : 7010 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-10-16 18:44:34

問題文

$N$ 頂点からなる木が与えられます。

頂点には $1$ から $N$ の、辺には $1$ から $N-1$ の番号がついており、辺 $i$ は頂点 $A_i$ と $B_i$ を双方向に結んでいます。

$(1,2,\dots,N)$ を並び替えて得られる順列 $P$ であって以下の条件を満たすものが存在するか判定してください。

  • 任意の $1$ 以上 $N$ 以下の相異なる整数の組 $(i,j,k)$ について以下の $2$ つの条件のうち少なくとも一方が成り立つ。
    • 頂点 $i$ から頂点 $j$ への単純パスに頂点 $k$ が含まれない。
    • 頂点 $P_i$ から頂点 $P_j$ への単純パスに頂点 $P_k$ が含まれない。

一つの入力ファイルにつき、 $T$ 個のテストケースに答えてください。

制約

  • 入力は全て整数である。
  • $1 \le T\le 10^5$
  • $3 \le N \le 10^5 $
  • $1 \le A_i,B_i \le N$
  • 与えられるグラフは木である。
  • $1$ つの入力ファイルについて、 $N$ の総和は $5\times 10^5$ 以下である。

入力

入力は以下の形式で標準入力から与えられる。
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
各テストケースは以下の形式で与えられる。
$N$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_{N-1}$ $B_{N-1}$

出力

$T$ 行出力してください。 $i\ (1\le i \le T)$ 行目には $i$ 番目のテストケースについて、条件を満たす順列 $P$ が存在するならば Yes を、そうでなければ No を出力してください。

サンプル

サンプル1
入力
3
4
1 2
2 3
2 4
5
1 2
2 3
3 4
4 5
7
1 3
6 2
2 5
3 7
7 4
5 1
出力
Yes
No
No

一つ目のテストケースでは、例えば $P=(2,1,3,4)$ が条件を満たします。

二つ目、三つ目のテストケースでは条件を満たす順列 $P$ が存在しないことが証明可能です。

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