No.768 Tapris and Noel play the game on Treeone
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 : polylogK / テスター : lumc_
タグ : / 解いたユーザー数 46
作問者 : polylogK / テスター : lumc_
問題文最終更新日: 2018-12-17 22:09:03
問題文
ある日 Noel ちゃんと Tapris ちゃんが友達の Treeone さんを使ってゲームをしました.
ゲームは次のルールに従います.
- 0. Treeone さんは頂点になにも書かれていない $N$ 頂点の木です.初めに Noel ちゃんが好きな頂点を 1 つ選び文字 "N" を書きます.
- 1. Tapris ちゃんが文字 "N" と書かれた頂点に隣接する頂点のうち,何も書かれていないものを 1 つ選び,文字 "T" を書きます.
- 2. Noel ちゃんが文字 "T" と書かれた頂点に隣接する頂点のうち,何も書かれていないものを 1 つ選び,文字 "N" を書きます.
- 3. 1 - 2 を繰り返します,これ以上書けなくなったほうが負けです.
Noel ちゃんは Tapris ちゃんに勝ちたいと思っています.
Tapris ちゃんの選択にかかわらず Noel ちゃんが勝つことのできる頂点をすべて求めてください.
入力
$N$ $a_1\ b_1$ $a_2\ b_2$ $\vdots$ $a_{N-1}\ b_{N-1}$
1 行目に木の頂点数 $N(2\le N\le 10^5)$ が与えられる.
2 行目以降 N - 1 行に $a_i$ と $b_i(1\le a_i,\ b_i\le N)$ が空白区切りで与えられ,辺$_i$ は頂点 $a_i$ と頂点 $b_i$ を結ぶ.
出力
1 行目に Noel ちゃんが最初に選ぶと勝てる頂点の個数を出力してください.
2 行目以降に Noel ちゃんが最初に選ぶと勝てる頂点を昇順で改行区切りで出力してください(最後の頂点の後にも改行を出力してください).
もしそのような頂点が 1 つもない場合は, 0
と出力してください.
サンプル
サンプル1
入力
6 1 2 1 3 2 4 2 5 2 6
出力
3 4 5 6
Noel ちゃんは 4, 5, 6 の頂点を選ぶことで Tapris ちゃんがどんな頂点を選んでも勝つことができます.
サンプル2
入力
5 1 2 1 5 2 3 3 4
出力
3 2 4 5
頑張ってください.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。