a224. Q_8_9 服務中心選位置

Content

有 $n$ 個小村莊以 $1 \sim n$ 編號，這些村莊以 $n - 1$ 條道路連接，每條道路都是雙向通行且連接兩個不同的村莊，已知從任兩個村莊之間都可以經由這些道路通達，兩個村莊稱為鄰近的村莊，如果它們之間有一條道路直接相連。

現在要選一些村莊成立服務中心，因為預算的關係無法每個村莊都成立一個服務中心，政府的政策決定：如果某個村莊沒有設服務中心，那麼他一定有一個鄰近的村莊有服務中心。也就是說，任何一個村莊最多只要經過一條道路就可以到達一個有設服務中心的村莊。請你計算至少需要成立幾個服務中心。

Input

第一行是正整數 $n$ ， $n > 1$ ，村莊以 $1 \sim n$ 編號。接下來有 $n - 1$ 行是道路的資料，每一行有兩個正整數 $u$ 與 $v$ ，代表有一條道路連接 $u$ 與 $v$ 。 $n$ 不超過 $10^{5}$ 。

Output

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

Sample Input #1

Sample Output #1

Sample Input #2

Sample Output #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (20%): 1.0s , <1K
公開測資點#1 (20%): 1.0s , <1K
公開測資點#2 (20%): 1.0s , <10M
公開測資點#3 (20%): 1.0s , <10M
公開測資點#4 (20%): 1.0s , <10M

Hint ：

範例一說明：設在 ${5, 2}$ 或 ${5, 1}$ 皆符合要求。範例二說明：這是 $7$ 個點排成一條路徑，選 ${2, 5, 7}$ 是一個解，兩個點一定無法滿足需求。

Tags:

ch8

出處:

Prof.Wu [管理者： zero(管理員) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」