P12806 题解 wukaichen888 · 2026-06-11 09:58:57 · 题解 不该评紫吗，全是经典 trick。 求出每条边被断开的时间，查询即为最大化路径最小值，Kruskal 重构树即可。 由于点的 x,y 坐标固定，所以断边时间为 |z_u-z_v| 首次大于一个阈值，其不难得到。 直接将绝对值拆开变成 z_u-z_v 和 -z_u+z_v 做两次。 考虑给整张图定向，u\to v 计算 z_u-z_v 的结果。 拿个线段树区间加，全局 check min 就可以维护。 你要给原图定向，最小化入度最大值，平面图最小度数 $\le5$，直接拓扑即可。