We first consider a binary search on the resulting unevenness. To check whether it is possible to have an unevenness of ~L~, let's run a DP on every tree in the forest, rooting each tree arbitrarily. Let ~dp_{i, j}~ be the minimum cost such that the longest path down from node ~i~ has a length of ~j~. Also, we have an array ~good~, which stores the minimum cost to let the subtree rooted at ~i~ be valid. For a child ~v~ of node ~u~ we have two transitions; we can cut the edge ~(u, v)~ or keep it. Let ~len_{u, v}~ and ~cost_{u, v}~ be the length and beauty of edge ~(u, v)~ respectively. If we cut the edge, then we simply let ~dp_{u, j} = dp_{u, j} + cost_{u, v} + good_v~. If we keep it, then we need to merge it with our current DP, so ~dp_{u, \max(i, j + len_{u, v})} = dp_{u, i} + dp_{v, j}~, taking care that ~i + j + len_{u, v}~ does not exceed ~L~.

At first, it seems like the complexity of our DP is horrid. After all, the size of the second dimension can be insanely large, and the second transition could square that large number. However, note that each node ~u~ has at most ~sz_u~ different values of ~j~, where ~sz_u~ is the number of nodes in the subtree of ~u~. Therefore, the amortized complexity of our algorithm is actually ~\mathcal{O}(N^2)~, using the same proof for the time complexity of tree convolutions!

We can implement the DP using a map for each node, for a total complexity of ~\mathcal{O}(N^2 \log 10^{12})~ with a moderate constant factor.