Maximizing Road Importance in a Construction-Affected Tree

The problem is defined on a tree with n intersections (nodes) connected by n-1 bidirectional roads (edges). For any two distinct intersections, the distance is the number of roads on the unique simple path connecting them (and 0 for the same intersection).

For each road (edge) connecting two nodes u and v, its importance is defined as follows. If the road is removed, the tree splits into two connected components with sizes A and B respectively. The importance of that road is given by $$importance = A \times B.$$

There is an additional twist: one intersection is under construction (but its location is unknown). The construction causes all intersections whose distance from the construction point is less than or equal to k (i.e. the closed set $$\{y : d(x,y) \le k\}$$ for a construction point x) to be closed. In addition, any road that is directly connected to a closed intersection becomes affected and cannot be used. The road’s importance value is defined with respect to the original tree as above.

Since the construction point is unknown, you need to consider the worst-case scenario. In other words, for every possible construction point x, let the sum of the importance values of all roads affected (roads with at least one endpoint in the closed set) be S(x). Your task is to compute the maximum possible value of S(x) over all choices of the construction point x.

Input and Output formats are given below.

inputFormat

The first line contains two integers n and k --- the number of intersections and the distance threshold for closure.

Each of the next n-1 lines contains two integers u and v (1-indexed) indicating that there is a road between intersections u and v.

outputFormat

Output a single integer --- the maximum possible sum of the importance values of roads affected by the construction, over all possible choices of the construction location.

sample

6 1
1 3
2 3
3 4
4 5
4 6

29