Kth-path

想定解は二分探索 + 重心分解です。
重心分解についての説明
類題

「$dist(u,v) \leq x$となる$(u,v) (1 \leq u < v \leq N)$が$K$個以上存在するか」という判定問題を考えます。
この判定問題は、$x$について単調性があるため、二分探索が使えます。判定問題の答えがYesとなるような最小の$x$がこの問題の答えです。

よって、この問題は、$dist(u,v) \leq x$となる$(u,v) (1 \leq u < v \leq N)$の数え上げに帰着されます。
この計算に重心分解を用います。重心を1つ選び、長さ$x$以下であって、重心を通るパスの数を数えます。

重心を始点として、bfs or dfsを行い、各頂点までの距離を計算します。$d(v)$を重心から頂点$v$までの距離とします。
$u < v$ かつ $d(u)+d(v) \leq x$となるような$(u,v)$の数を数えます。これは各$d(v)$をソートした列に対する尺取り法 or 二分探索で計算出来ます。

このままでは、重心を通らないようなパスについても数えているため、重心を取り除いた時に同じ部分木に属する$(u, v)$であって、
$u < v$ かつ $d(u)+d(v) \leq x$となるような$(u, v)$の数を引きます。

これによって、長さ$x$以下で、重心を通るパスの数の計算が出来ました。重心を取り除いて出来る各部分木についても再帰的に数え上げを行います。

二分探索の判定部分で、毎回重心分解をし、$d(v)$のソートを行うと計算量は、$O(N * log^2N * log(Nmax(w_i)))$になりますが、
初めに重心分解を1度だけしておき、$d(v)$のソート結果を保持した状態で、二分探索をすることで、計算量を$O(N * logN * log(Nmax(w_i)))$にすることが出来ます。