TopCoder

Thumb 100
Ken
廢到不行

User's AC Ratio

90.5% (19/21)

Submission's AC Ratio

37.7% (26/69)

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) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 1000 65536 262144
9 1000 65536 262144