Problem
n 個の頂点からなるツリー (接続された非巡回無向グラフ) が与えられます。
その最大一致のサイズ (対の非隣接エッジのセット) を見つけます。
入力:
最初の行には、ツリー内の頂点の数 n が含まれています。
次に n-1 行が続き、各行には 2 つの数値 a
i と b
i (1 <= a
i, b
>i <= n) - ツリー エッジ。
出力:
数値を 1 つ出力 - 与えられたツリーの最大マッチングのサイズ。
例:
<本体>
| 入力 |
出力 |
4
1 2
23
3 4 |
2 |
説明:
このツリーの最大一致には、エッジ 1-2 および 3-4 が含まれます。