P2977 [USACO10JAN] Cow Telephones G

The cows have set up a telephone network, which for the purposes of this problem can be considered to be an unrooted tree of unspecified degree with $N$ ($1 \le N \le 100{,}000$) vertices conveniently numbered $1\dots N$. Each vertex represents a telephone switchboard, and each edge represents a telephone wire between two switchboards. Edge $i$ is specified by two integers $A_i$ and $B_i$ the are the two vertices joined by edge $i$ ($1 \le A_i \le N$; $1 \le B_i \le N$; $A_i \ne B_i$). Some switchboards have only one telephone wire connecting them to another switchboard; these are the leaves of the tree, each of which is a telephone booth located in a cow field. For two cows to communicate, their conversation passes along the unique shortest path between the two vertices where the cows are located. A switchboard can accomodate only up to $K$ ($1 \le K \le 10$) simultaneous conversations, and there can be at most one conversation going through a given wire at any one time. Given that there is a cow at each leaf of the tree, what is the maximum number of pairs of cows that can simultaneously hold conversations? A cow can, of course, participate in at most one conversation.

\* Line $1$: Two space separated integers: $N$ and $K$. \* Lines $2\dots N$: Line $i+1$ contains two space-separated integers: $A_i$ and $B_i$.

\* Line $1$: The number of pairs of cows that can simultaneously hold conversations.

```plain 1 5 C1 C5 | | || || 2---4 --> |2---4| | | || || 3 6 C3 C6 ``` Consider this six-node telephone tree with $K=1$: There are four cows, located at vertices $1$, $3$, $5$ and $6$. If cow $1$ talks to cow $3$, and cow $5$ talks to cow $6$, then they do not exceed the maximum number of conversations per switchboard, so for this example the answer is $2$ (for two pairs of cows talking simultaneously).