注意到点分治。
如果路径是 \(u, a_2,a_3, \cdots, a_{m-1}, v\)，那么 \(val (u, v) = \frac{\sum a}{m}\)，要让 \(val(u, v)\) 尽可能接近 \(k\)。
考虑二分 \(|val(u,v)-k|\) 的值 \(x\)，要判定是否有 \(|val(u,v)-k| \ge x\)。
\[|val(u,v)-k| \ge x\\
|\frac{\sum_i(a_i)-km}{m}|\ge x\\
| \sum_i(a_i) - km | \ge mx\\
|\sum_i(a_i-k)|\ge mx\]
\(O(n)\) 记录出 \(dis\) 之后需要解决的就是有 \(n\) 个 \(dis\)，判定是否有 \(|dis_u + dis_v| \ge mx\)，而这个实际上可以 \(O(n)\) 解决，依次遍历重心的儿子，答案一定是两个 \(max\) 加或者两个 \(min\) 加。
复杂度 \(O(n\log n \log k)\)。