题解：CF1566G Four Vertices

SegTree · 2025-10-14 16:47:52 · 题解

这题看上去就是分类讨论即可。

如果两条最短的边无公共点，答案就是这两条边的长度之和。

否则让我们考虑第三条边，如果与第一条边无公共点，那么答案就是第一条与第三条的长度之和。

由于没有重边，剩下的 case 就是菊花和三元环。

引理：答案一定包含这三条边中至少一条。

证明：如果不是，那么一定能删去一条边并调整为这三条边中任意一条。

菊花的时候可以构造出前三条边之和，否则，我们只需计算钦定端点既不是 x 也不是 y 的最短的边。给每个点开个值域线段树 XOR Hash 一下，非 0 就认为有边，因为要求端点不是 x 也不是 y，就用总的异或 x 和 y 两颗子树即可。

不咋好写，时间复杂度 O(q(\log n+\log q)。

但是事实上，用线段树维护 XOR Hash 是不必要的，可以发现一条边在它的两个端点有一个权值排不进前三就没有用，因此可以开 set 暴力维护，感觉比较好写。

https://codeforces.com/contest/1566/submission/343664951。