有 $n$ 個小村莊以 $1 \sim n$ 編號，這些村莊以 $n-1$ 條道路連接，每條道路都是雙向通行且 連接兩個不同的村莊，已知從任兩個村莊之間都可以經由這些道路通達，兩個村莊稱為鄰近的村莊，如果它們之間有一條道路直接相連。
現在要選一些村莊成立服務中心， 因為預算的關係無法每個村莊都成立一個服務中心，政府的政策決定：如果某個村莊沒有設服務中心，那麼他一定有一個鄰近的村莊有服務中心。也就是說，任何一個村莊最多只要經過一條道路就可以到達一個有設服務中心的村莊。請你計算至少需要成立幾個服務中心。
第一行是正整數 $n$，$n>1$，村莊以 $1 \sim n$ 編號。接下來有 $n-1$ 行是道路的資料，每一行有兩個正整數 $u$ 與 $v$，代表有一條道路連接 $u$ 與 $v$。$n$ 不超過 $10^5$。
最少需要成立的服務中心數量。
5 1 2 5 1 5 3 5 4
2
7 1 2 2 3 4 3 5 4 5 6 7 6
3
範例一說明：設在$\{5,2\}$或 $\{5,1\}$皆符合要求。 範例二說明：這是 $7$ 個點排成一條路徑，選 $\{2,5,7\}$是一個解，兩個點一定無法滿足 需求。
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||