题解：P16445 [XJTUPC 2026] The Whole Rest

DGH_Didi · 2026-05-11 13:15:16 · 题解

树上启发式合并做法

思路

首先注意到路径最小代价显然为 0，而又要经过树上的所有点，最小化路径长度实际上等价于选两个点 u, v，使得该路径长度最大且路径上权值的异或和为 0。

选顶点 1 作为树的根，深搜求出从根到每个节点 u 的路径异或和 val_u，则两个节点 u, v 间路径异或和为 val_u \oplus val_v，而若预处理出深度数组 dep，则两点的路径长度为 dep_u + dep_v - 2 \times dep_{lca(u,v)}。

考虑从子节点向父节点合并的过程，使用 map 记录每个节点子树中相同 val_u 的最大深度节点对应的编号，则每次将儿子向父亲启发式合并的过程可以顺便计算出最大路径长度。

构造路径的部分使用深搜即可，我的做法是先走非两点路径上的点，再走路径上的点，总时间复杂度 O(n \log^2 n)，使用哈希表可以做到 O(n \log n)。

::::info[代码]

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
using i64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    vector<vector<pair<int, int>>> e(n + 1);
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
    }

    vector<map<int, int>> mp(n + 1);
    vector<int> dep(n + 1, 0);

    int u = 1, v = 1, mx = 0;
    auto merge = [&](int x, int y) {
        if (mp[x].size() > mp[y].size()) {
            mp[y].swap(mp[x]);
        }
        for (auto [val, id] : mp[x]) {
            if (mp[y].contains(val)) {
                int U = mp[y][val], V = id;
                int now = dep[U] + dep[V] - 2 * dep[y]; // y 此时肯定是 LCA
                if (now > mx) {
                    mx = now;
                    u = U, v = V;
                }
                if (dep[U] < dep[id]) {
                    mp[y][val] = id;
                }
            } else {
                mp[y][val] = id;
            }
        }
        mp[x].clear();
    };

    auto dfs = [&](auto &&self, int u, int f, int val) -> void {
        dep[u] = dep[f] + 1;
        mp[u][val] = u;
        for (auto &[v, w] : e[u]) {
            if (v == f) {
                continue;
            }
            self(self, v, u, val ^ w);
            merge(v, u);
        }
    };
    dfs(dfs, 1, 0, 0);

    vector<bool> onPath(n + 1, false);
    auto dfs2 = [&](auto &&self, int u, int f) -> void {
        if (u == v) {
            onPath[u] = true;
            return;
        }
        for (auto &[vv, w] : e[u]) {
            if (vv == f) {
                continue;
            }
            self(self, vv, u);
            if (onPath[vv]) {
                onPath[u] = true;
                return;
            }
        }
    };
    dfs2(dfs2, u, 0);

    vector<int> path;
    auto dfs3 = [&](auto &&self, int u, int f) -> void {
        path.push_back(u);
        for (auto [v, w] : e[u]) {
            if (v == f || onPath[v]) {
                continue;
            }
            self(self, v, u);
            path.push_back(u);
        }
        for (auto [v, w] : e[u]) {
            if (onPath[v] && v != f) {
                self(self, v, u);
                break;
            }
        }
        if (u == v) {
            return;
        }
    };
    dfs3(dfs3, u, 0);

    cout << path.size() << endl;
    for (auto i : path) {
        cout << i << " ";
    }
    return 0;
}

::::