TopCoder

Thumb 100
Ken
廢到不行

User's AC Ratio

93.8% (15/16)

Submission's AC Ratio

34.5% (20/58)

Description

我們定義佔領一條邊的意思是:一條邊的兩個點有一個點被佔領。

現在給你一顆樹,你要學華盛頓把他砍倒,砍倒的首要目的:就是要佔領所有的邊。

問你最少要攻佔幾個點,才能達到首要目的。

Input Format

$第一行為一個正數字n。(n\leq 10000) $

$接著有n-1個行,每行兩個正整數a,b,代表a頂點到b頂點之間有一條邊。$

$頂點編號是1到n。$

Output Format

輸出一個貌似答案的正整數。

Sample Input

5
1 3
5 2
4 3
3 5

Sample Output

2

Hints

Problem Source

原TIOJ1292 / 雄中公假社'08 入退社考。(minimum vertex cover problem)。Problem Setter:ggm。

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536
5 1000 65536
6 1000 65536
7 1000 65536
8 1000 65536
9 1000 65536