木の塗り分け C編（paizaランク B 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ポスト
問題
下記の問題をプログラミングしてみよう！
頂点数 n の木が与えられます。
以下の条件を満たすように根の頂点を赤または青に塗り分けるとき、赤に塗られた頂点の個数の最大値を求めてください。
・ 任意の連続する長さ 1 以上のパスについて、必ず (そのパスに含まれる赤に塗られた頂点の個数) <= (そのパスに含まれる青に塗られた頂点の個数) が成り立つ。
- 入力される値
-
n
a_1 b_1
a_2 b_2
...
a_{n-1} b_{n-1}
・ 1 行目に、木の頂点数を表す整数 n が与えられます。
・ 続く n-1 行に、整数 a_i, b_i が半角スペース区切りで与えられます。これは、a_i 番目の頂点と b_i 番目の頂点が辺で結ばれていることを表します。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
1 行で、答えを整数で出力してください。
また、末尾に改行を入れ、余計な文字を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 1 ≦ n ≦ 10000 = 10^4
・ 1 ≦ a_i, b_i ≦ n (1 ≦ i ≦ n-1)
・ a_i ≠ b_i (1 ≦ i ≦ n-1)
・ (a_i, b_i) ≠ (a_j, b_j) かつ (b_i, a_j) ≠ (a_j, b_j) (1 ≦ i, j ≦ n-1, i ≠ j)
・ 与えられるグラフは木である
- 入力例1
-
7
1 2
2 3
1 4
4 5
1 6
6 7
- 出力例1
-
3
- 入力例2
-
6
1 2
1 3
1 4
4 5
4 6
- 出力例2
-
2
