問題一覧 > 通常問題

No.1295 木と駒

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 9
作問者 : 沙耶花沙耶花 / テスター : 👑 QCFiumQCFium
1 ProblemId : 4394 / 出題時の順位表
問題文最終更新日: 2020-11-21 19:14:58

問題文

$N$ 頂点の木があります. 各 $i(1 \le i \le N-1)$ に対し, $i$ 番目の辺は $a_i$ 番目の頂点と $b_i$ 番目の頂点を結んでいます.

沙耶花はこの木と1個の駒を使ってゲームをすることにしました.
以下, ゲーム中に駒が一度でも置かれていたことがある頂点を「訪問済みの頂点」, そうでない頂点を「未訪問の頂点」と呼ぶことにします.

沙耶花はゲームの初めにコマを $x$ 番目の頂点に置いた後, 次の2種類の操作を好きな順番で何度でも行うことができます.

  • 現在駒が置かれている頂点に隣接する未訪問の頂点のうち, 番号が最小の頂点に駒を移動させる
    (そのような頂点が存在しない場合, 何もしない)
  • 現在駒が置かれている頂点に隣接する訪問済みの頂点のうち, 番号が最小の頂点に駒を移動させる
    (そのような頂点が存在しない場合, 何もしない)

このゲームの目的はすべての頂点を訪問済みの頂点にすることです.
$x=1,2,...,N$の場合それぞれについてこれが達成可能かを判定してください.

入力

$N$
$a_1\ b_1$
$\vdots$
$a_{N-1}\ b_{N-1}$

  • $2 \le N \le 10^5$
  • $1 \le a_i,b_i \le N$
  • 入力はすべて整数
  • 与えられるグラフは木である

出力

$N$行出力してください
$i$行目には$x=i$の場合において目的が達成可能ならばYesと, そうでなければNoと出力してください.
最後に改行してください.

サンプル

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

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