Little Petya likes painting trees a lot. There is a big tree in front of his house which has N vertices
numbered from 1 to N . The root of this tree is located at the vertex with the number 1. Initially Petya
is situated near the root of the tree. In order to paint it, he starts climbing, each time coloring an edge
which he passes along it. He always climbs up, increasing distance to the root. When he ends up in some
leaf of the tree, he jumps off to its root. Then he can start climbing again. As Petya’s power is limited,
he cannot start climbing from the root more than M times.
Petya wishes to determine the maximum number of edges he can paint. You are to help Petya finding
that value. Note that each painted edge is counted only once, even if it has been painted more than one
time.
Input consists of multiple blocks of test cases,
and is ended with EOF. Each block consists of the following:
The first line of input contains two integers N and M (1 ⩽ N ⩽ 100 000, 0 ⩽ M ⩽ 100 000).
Each of the next N − 1 lines contains two integers xi , yi (1 ⩽ xi , yi ⩽ N ) — numbers of vertices connected
by an edge.
It is guaranteed that the given graph is connected, thus forming a tree.
For each test case output the maximum number of edges Petya can paint if he climbs the tree no more than M times.
8 3 1 3 1 2 2 4 2 5 4 6 4 7 5 8
6
Migrated from old NTUJ.
Petrozavodsk training camp, 2010
| No. | Testdata Range | Score |
|---|