Cow Telephones

The cows have built a telephone network. For this problem it can be viewed as an undirected tree with $N$ vertices ($1 \le N \le 100{,}000$), numbered $1$ through $N$. Each vertex is a telephone switchboard, and each edge is a telephone wire joining two switchboards. Edge $i$ is given by two integers $A_i$ and $B_i$, the two vertices it connects ($1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$).

Some switchboards have exactly one wire connecting them to another switchboard; these are the leaves of the tree, and each leaf is a telephone booth in a cow field.

For two cows to talk, their conversation travels along the unique shortest path between the two vertices where the cows stand. A single switchboard can handle at most $K$ simultaneous conversations ($1 \le K \le 10$), and at most one conversation may pass through any given wire at any one time.

Given that there is one cow at every leaf of the tree, what is the maximum number of pairs of cows that can talk at the same time? Each cow may take part in at most one conversation.

Consider this six-vertex telephone network with $K = 1$:

       1   5          C1   C5
       |   |          ||   ||
       2---4   -->    |2---4|
       |   |          ||   ||
       3   6          C3   C6

There are cows at vertices $1, 3, 5,$ and $6$. If cow $1$ talks to cow $3$ and cow $5$ talks to cow $6$, no switchboard exceeds its limit, so the answer for this example is $2$ (two pairs of cows talking simultaneously).

• Line 1: Two space-separated integers $N$ and $K$.
• Lines 2 to $N$: Line $i+1$ contains two space-separated integers $A_i$ and $B_i$ for edge $i$.

• Line 1: The maximum number of pairs of cows that can hold conversations simultaneously.