Treeland Exhibition

Time Limit: 2 Seconds
Memory Limit: 32768 KB

There are *n* towns in the treeland and they form a tree, as you may guess, i.e. there is a unique path between every pair of towns. The length of road connecting every pair of adjacent towns is always 1 unit.

You want to hold an exhibition simultaneously on no more than *L*+1 consecutive towns, i.e. you
choose two towns *u* and *v* of no more than *L* unit apart, and set up your exhibition in all the
towns on the unique path from *u* to *v*. You want to attract people from all over the treeland to
your exhibition, so you'd like to minimize the sum of "travelling distance" from every town.
The "travelling distance" of a town is the distance from that town to its closest exhibition-town.

**Input**

There are at most 25 test cases. Each case begins with two integers, *n* and *L* (*n* <= 10000, 0 < *L* <= 100),
the number of towns, and the maximal distance of the "endpoint towns" you choose. Next *n*-1 lines contain
the descriptions of connections, each with two integers *a* and *b*, indicating that town *a* and town *b* are
directly connected (towns are numbered from 0 to *n*-1). The input ends with *n* = *L* = 0.

**Output**

For each test case, print the minimal sum of travelling distance.

**Sample Input**

3 1
0 1
1 2
4 1
0 1
1 2
2 3
0 0

**Sample Output**

1
2

Author:

**LIU, Rujia**
Source:

**The 34th ACM-ICPC Asia Regional 2009 Ningbo Site NIT Cup National Invitation Contest**
Submit
Status