Optimal blue-red tree P24951


Statement
 

pdf   zip

html

You are given an undirected connected graph with no cycles. You must paint every node either blue or red. Painting in blue costs 1 per node, while painting in red costs 2 per node. Your goal is to minimize the total cost of painting the tree. There is just one restriction: Each node can have, at most, one adjacent node with the same color than itself.

Input

Input consists of several trees, each one with the number of nodes n, followed by n − 1 pairs x y for the edges. Nodes are numbered from 0. Assume 1 ≤ n ≤ 105.

Output

Print the minimum cost to color each tree.

Public test cases
  • Input

    1
    3  0 1  1 2
    5  0 1  1 2  2 3  3 4
    8  3 7  7 4  0 6  6 1  7 6  2 6  5 7
    

    Output

    1
    4
    6
    10
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++