C. Leaf Partition
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree of $$$N$$$ nodes, and an integer $$$K$$$.

Your task is to partition the leaves of the tree into $$$K$$$ groups while respecting the following:

  • a group's valid tour is a path that starts from any leaf of that group, reaches all other leaves of the same group then goes back to its starting point.
  • a group's cost is the minimal traveled distance among all valid tours of that group.
  • The cost of a partition is the sum of its groups' costs.
  • The cost of the partition should be minimal
Input

The first line contains two integers $$$N$$$ and $$$K$$$ ($$$3 \leq N \leq 10000, 2 \leq K \leq 20$$$)

The next $$$N-1$$$ lines contain two space separated nodes representing an edge $$$u$$$ $$$v$$$ ($$$ 1 \leq u, v \leq n$$$)

Output

A single integer, the minimal cost of a partition among all possible partitions into $$$K$$$ groups.

Scoring
  • (10 points) $$$3 \leq N \leq 30$$$ and $$$2 \leq K \leq 4$$$
  • (20 points) $$$K = 2$$$
  • (30 points) $$$K = 3$$$
  • (40 points) No additional constraints
Example
Input
10 2
10 6
2 10
3 10
4 10
1 2
5 6
8 9
4 8
5 7
Output
12