CF2057E2。

声明：本题解的撰写受到了deepseek与qwen的在思路上的帮助，但所有文字与公式全部由本人独立撰写，可以放心食用。

这题要求对于每个询问 $(a,b,k)$，在 $a$ 到 $b$ 的所有路径中，找到路径上边权第 $k$ 大值的最小值。直接枚举路径显然不行。

我们考虑二分答案 $x$。

一条路径的第 $k$ 大边权 $\le x$，当且仅当路径上边权 $>x$ 的边数不超过 $k-1$。

所以问题等价于：找最小的 $x$，使得存在一条 $a$ 到 $b$ 的路径，其中边权 $ >x $ 的边数 $ < k $。

这就相当于，把边权 $\le x$ 的边看成免费的，边权 $>x$ 的边看成收费的，问从 $a$ 到 $b$ 最少要走几条收费边。

预处理。

初始时，没有任何树边免费，所有边的费用都是 1。

我们先用 Floyd 求出任意两点间的最少边数，记为 $d[0][i][j]$。

跑Kruskal。假设新加入的树边是 $(u,v)$，它的费用从 1 变成 0。因为新边费用为 0，其他费用非负，所以最优路径最多用一次这条新边。于是转移就是：

$$d[c][i][j]=\min(d[c-1][i][j],d[c-1][i][u]+d[c-1][v][j],d[c-1][i][v]+d[c-1][u][j])$$

同时我们记录 $val[c]$ 为第 $c$ 条加入的 Kruskal 树边的权值。因为边已经按权值排序，所以 $val$ 数组是单调不减的。

处理完所有树边后，对于每个询问 $(a,b,k)$，我们只需要找到最小的 $c$，使得 $ d[c][a][b] < k $，二分即可。答案就是 $ val[c] $。

时间复杂度 $O(N^3+Q\log N)$。