服務中心選位置 (AP325 Q-8-9)

有 \(n\) 個小村莊以 \(1 \sim n\) 編號，這些村莊以 \(n-1\) 條道路連接，每條道路都是雙向通行且連接兩個不同的村莊，已知從任兩個村莊之間都可以經由這些道路通達。兩個村莊稱為鄰近的村莊，如果它們之間有一條道路直接相連。現在要選一些村莊成立服務中心，因為預算的關係無法每個村莊都成立一個服務中心，政府的政策決定：如果某個村莊沒有設服務中心，那麼它一定有一個鄰近的村莊有服務中心。也就是說，任何一個村莊最多只要經過一條道路就可以到達一個有設服務中心的村莊。請你計算至少需要成立幾個服務中心。

輸入格式

第一行是正整數 \(n\)，村莊以 \(1 \sim n\) 編號。接下來有 \(n-1\) 行是道路的資料，每一行有兩個正整數 \(u\) 與 \(v\)，代表有一條道路連接 \(u\) 與 \(v\)。同一行的數字以一個空白隔開。

限制

• \(2 \le n \le 10^5\)。
• \(1 \le u, v \le n\)，\(u \ne v\)；保證任兩個村莊之間都可以經由道路互相到達。

輸出格式

最少需要成立的服務中心數量。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

5
1 2
5 1
5 3
5 4

範例輸出 1

2

範例輸入 2

7
1 2
2 3
4 3
5 4
5 6
7 6

範例輸出 2

3

範例說明

範例一：設在 \(\{5, 2\}\) 或 \(\{5, 1\}\) 皆符合要求。

範例二：這是 \(7\) 個點排成一條路徑，選 \(\{2, 5, 7\}\) 是一個解，兩個點一定無法滿足需求。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 8 章 Q-8-9，第 298 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。