Tree Height Reduction

Time limit2sMemory limit128 MB

Summary

Given a rooted tree and target height H, find the minimum total cost of repeatedly reattaching vertices to ancestors (cost based on level gap) to bring the tree height down to at most H.

Level: Hard8 of 10
Topics: Tree, Dynamic programming, Greedy, DFS
Solved: No attempts yet

Problem

In a rooted tree, the level of a vertex V is the distance from the root to V. A vertex U is the parent of a vertex V when U and V are connected by an edge and the level of U is exactly 1 less than the level of V.

You may perform the following reconnection operation any number of times.

Choose a non-root vertex V.
Choose a vertex U that is an ancestor of V.
Remove the edge between V and its current parent.
Connect U and V with an edge, making U the new parent of V.

The cost of an operation is the level difference between the two chosen vertices, minus 1, measured immediately before the operation. If V has level L1 and U has level L2 immediately before the operation, the cost is L1 - L2 - 1.

The height of a tree is K when at least one vertex has level K and no vertex has level K + 1. Given a rooted tree and a target height H, find the minimum total cost needed to make the height of the tree at most H. You may perform multiple operations.

Input

The first line contains the number of vertices N. (1 <= N <= 100)

Each of the next N - 1 lines contains an edge of the tree in the form a b, meaning that a is the parent of b.

The vertices are numbered from 0 to N - 1, and the root is always vertex 0.

The last line contains the target height H. H is an integer between 1 and N - 1, inclusive.

Output

Print the minimum total cost required to make the height of the tree at most H.

Examples4

Example 1
Input
```
5
0 1
1 2
2 3
2 4
2
```
Expected output
```
1
```
Example 2
Input
```
5
0 1
1 2
2 3
2 4
1
```
Expected output
```
3
```
Example 3
Input
```
3
0 1
1 2
2
```
Expected output
```
0
```
Example 4
Input
```
9
0 3
3 1
1 8
8 6
2 7
4 2
0 4
7 5
3
```
Expected output
```
2
```