题解：CF858F Wizard's Tour

LinkCatTree · 2026-11-05 13:50:29 · 题解

题意即为：找出最多的端点相交的边二元组且不得重复使用边。

类似的构造问题都可以尝试考虑 dfs 生成树。

手玩一下我们发现：对于一个包含 m 条边的连通块总是存在一种方案取到 \lfloor\frac m2\rfloor 对边。为了方便构造，我们加强一下结论，并将其放到树上：

我们声称，一定存在一种构造方式，对于 dfs 树上 u 的子树，其中所有树边和两端都在子树中的返祖边都能被两两配对，至多剩下一条一端为 u 的边。

考虑归纳证明这个结论。

我们考虑点 u 的每个儿子 v，如果有边剩余可以与 (u, v) 配对；否则维护一个边集 E_u 表示在 u 上要考虑的所有树边，将 (u, v) 放入 E_u 中。

再考虑所有 u 为较浅端点的返祖边，和 E_u 放在一起考虑。显然所有边都有共同端点 u，所以两两配对即可，不难发现至多只剩下了一条一端为 u 的边。

构造部分代码：

int dfs (int u, int fa) {
    dfn [u] = ++tim;
    vector <int> vets;
    for (const int v : edg [u]) {
        if (v == fa)
            continue ;
        if (dfn [v] && dfn [v] > dfn [u])
            vets.emplace_back (v);
        else if (!dfn [v]) {
            int k = dfs (v, u);
            if (k)
                ans.emplace_back (u, v, k);
            else
                vets.emplace_back (v);
        }
    }
    for (int i = 0; i + 1 < (int) vets.size (); i += 2)
        ans.emplace_back (vets [i], u, vets [i + 1]);
    return ((int) vets.size () & 1) ? vets.back () : 0;
}