## poj3659

maksyuki 发表于 oj 分类，标签: ,

Cell Phone Network

Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1..N) so they can all communicate.

Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ NA ≠ B) there is a sequence of adjacent pastures such that is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.

Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.

Input

* Line 1: A single integer: N
* Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B

Output

* Line 1: A single integer indicating the minimum number of towers to install

Sample Input

5

1 3

5 2

4 3

3 5

Sample Output

2

Source

USACO 2008 January Gold

dp[u][1] += min (dp[v][1], dp[v][2], dp[v][3])

dp[u][3] += min (dp[v][1], dp[v][2])

(1)dp[u][2] = INF(若u是叶子节点)

(2)dp[u][2] = 若选择了的u所有子节点中有dp[v][1]则计算完后直接返回即可，反之则使用一个变量来记录dp[v][1] - dp[v][2]的最小值，最后循环完之后再加上这个变量的值