把所有边边权减去 $k$，则即寻找一条路径满足平均值的绝对值最小。

我们二分答案，看是否有 $-w\sim w$ 的解。

分别把边权加 $w$ 和减 $w$，即为判定是否有路径在前一张图上权值非负后一张图上权值非正。

点分治，考虑经过当前分治中心的路径，就是对不同子树之间判断有无二维偏序。

使用二叉点分治，在归并的同时维护单调栈，即可快速判断。

注意由于向下取整，还要判是答案刚好为整数的情况。

总复杂度大概带 $3$ 只 $\log$？

参考代码。