Problems Base course RU

Guarding an exhibition

An exhibition occupies n halls connected by passages so that from any hall to any other there is exactly one path without repetitions: the halls and passages form a tree. A guard standing in a hall sees all the passages leading out of that hall. What is the smallest number of guards needed so that every passage is seen?

The trees in the tests can be very deep, up to a single long enfilade of two hundred thousand halls.

Input

The first line holds n (1 ≤ n ≤ 200,000). Then n − 1 lines of two numbers a and b (1 ≤ a, b ≤ n): a passage between halls a and b.

Output

A single number: the smallest number of guards.

Examples

Example 1

Input

Output

Example 2

Input

Output

Limits

Time · Python: 2000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 9 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

Putting a guard where there are the most passages is reasonable, but in the first example it gives four guards, while three are enough. Hang the tree from any hall. What do you need to know about a hall’s subtree to solve the problem for its parent?

2Hint 2

One thing matters for a subtree: whether there is a guard at its root. That decides whether the parent needs a guard to see the passage between them.

3The idea

For each hall v, two numbers: guard[v], how many guards its subtree needs if there is a guard in v itself, and free[v], if there is not. If there is a guard in v, the passages to the children are already seen, and for each child we take the better of the two: guard[v] = 1 + Σ min(guard[c], free[c]). If not, each passage to a child must be seen from the child’s side: free[v] = Σ guard[c]. The answer is min(guard, free) at the root. This is dynamic programming on trees.

4Walkthrough

Children must be computed before the parent. A recursive traversal ensures this, but in Python on an enfilade of two hundred thousand halls it hits the recursion depth limit, and a raised limit hits the stack size. Without recursion is more reliable: traverse the tree breadth-first from hall 1, remembering parents, and walk the resulting list backwards; then each hall comes after all its descendants and immediately hands its two numbers to its parent.

In the first example the central hall has three corridors of two halls each. A guard in the centre sees three passages, but one passage remains in each corridor, and three more guards are needed, four in all. Yet three guards in the middle halls of the corridors see all six passages. On the tree of this site’s addresses, with 8986 nodes, 116 guards are enough.

4+Solution

5Complexity

O(n): each hall enters the traversal once and hands its numbers to its parent once. On an arbitrary graph this problem, the minimum vertex cover, is NP-hard; on a tree it is made easy by the fact that subtrees are not connected to each other.

6Common mistakes

The busiest hall first. Fails the first example: the centre with three passages looks advantageous but leaves three uncovered passages in different places.
Recursion in Python. On a long enfilade, a RecursionError or a crash from the stack, even if the algorithm is correct.
One number per hall. Without separating “with a guard / without”, the parent cannot tell whether the passage to a child is seen.

Algorithms behind it

DP Technique Dynamic programming on trees A subtree’s answer from its children’s answers: a pass from the leaves to the root, and for all roots at once, rerooting. O(n) 2 problems GRA Algorithm Depth-first search Goes deep, marks each vertex's entry and exit and finds cycles by them in O(V + E). O(V + E) 2 problems