题目解析

问题重述

有一棵包含 $2n$ 个节点的树，每个节点有一个 $1$ 到 $n$ 的权值，每个权值恰好出现两次。每个节点 $i$ 的代价为 $2^i$（非常大，按二进制可以比较字典序）。需要选择一个连通子集，使得每个权值至少出现一次，并且总代价最小。输出子集的节点集合。

核心思想

1. 代价函数的性质

由于节点 $i$ 的代价是 $2^i$，比较两个子集的总代价等价于比较它们按节点编号降序排列的二进制表示。这意味着：要让总代价最小，应该尽量不选编号大的节点。换句话说，按编号从大到小贪心地决定是否选择每个节点：能跳过就跳过，必须选才选。

2. 贪心策略

按节点编号从大到小处理：

• 如果当前节点可以不选（存在一个合法的连通子集不包含它），则跳过它
• 否则必须选它

问题转化为：如何判断一个节点 $v$ 是否必须选？

3. 确定根节点

首先，权值为 $1$ 的两个节点中至少有一个必须选。我们分别以这两个节点为根，计算两种情况下的答案，然后取代价更小的那个。

4. 在根确定的树中判断

假设根一定在子集中。那么对于任何被选的节点，其到根的路径上的所有节点也必须在子集中（否则子集不连通）。这给了我们一个传递关系：选子节点 $\Rightarrow$ 必须选父节点。

5. 标记“必须选”的节点

对于每个权值 $x$，它的两个节点 $u$ 和 $v$ 必须至少有一个在子集中。为了最小化代价，我们会尽量选深度更深的那个（因为深度越深编号可能越小？等等，这里编号是固定的，不是按深度）。实际上，我们需要精确处理。

一种方法：先标记所有从 LCA 到根路径上的节点为“必须选”。因为如果两个节点都在子树中，它们的 LCA 到根路径必须全部被选才能连通到根。

6. 两种状态

每个节点有三种状态：

• 1：必须选
• -1：禁止选
• 0：未确定

初始时根为 1。然后对于每个权值，标记其两个节点的 LCA 到根的路径为 1。

7. 处理“禁止选”的节点

当我们决定不选某个节点 $v$ 时（状态设为 -1），它的整个子树都不能选（否则不连通）。并且在子树中，如果某个权值原本打算靠该节点来覆盖，则现在必须靠该权值的另一个节点来覆盖，需要标记另一个节点到根的路径为 1。

这个过程可以用 BFS 实现：标记子树内所有未确定节点为 -1，并且对于遇到的每个节点的权值，标记另一个节点到根的路径为 1。

8. 实现细节

• 使用 LCA 快速找到两个节点的最近公共祖先
• 使用 mark 函数标记从节点到根的路径为 1（遇到已标记节点停止，总复杂度 $O(n)$）
• 使用 markdel 函数 BFS 遍历子树标记为 -1，并调用 mark 处理另一个同权值节点
• 对于每个可能的根（两个权值为 $1$ 的节点），执行该过程得到候选解
• 比较两个候选解的大小（按节点编号降序的二进制串），取较小的

算法步骤

1. 读入 $n$，读入 $2n$ 个权值，建图
2. 找到权值为 $1$ 的两个节点 $rt_1, rt_2$
3. 对每个根 $rt \in \{rt_1, rt_2\}$：
   • 以 $rt$ 为根，预处理 LCA
   • 初始化状态数组 $state$ 全为 $0$
   • 对于每个权值 $x$，标记 $\text{LCA}(l[x], r[x])$ 到根的路径为必须选
   • 按节点编号从大到小遍历，如果状态为 $0$，则将其子树全部标记为禁止选，并处理依赖
   • 记录状态为 $1$ 的节点作为候选解
4. 比较两个候选解，选择二进制表示更小的（即节点编号大的尽量不选）
5. 输出结果

代码实现

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g;

struct LCA {
    vector<int> d, fst, par;
    vector<pair<int, int>> ord;
    vector<vector<pair<int, int>>> st;
    vector<int> pw;

    void build(vector<pair<int, int>> a) {
        int n = a.size();
        int lg = 32 - __builtin_clz(n);
        st.resize(lg, vector<pair<int, int>>(n));
        st[0] = a;
        for (int j = 1; j < lg; ++j) {
            for (int i = 0; i < n; ++i) {
                st[j][i] = st[j - 1][i];
                if (i + (1 << (j - 1)) < n)
                    st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]);
            }
        }
        pw.resize(n + 1);
        for (int i = 2; i <= n; ++i)
            pw[i] = pw[i / 2] + 1;
    }

    int lca(int v, int u) {
        int l = fst[v], r = fst[u];
        if (l > r) swap(l, r);
        ++r;
        int len = pw[r - l];
        return min(st[len][l], st[len][r - (1 << len)]).second;
    }

    void init(int v, int p = -1) {
        if (fst[v] == -1) fst[v] = ord.size();
        ord.push_back({d[v], v});
        for (int u : g[v]) if (u != p) {
            par[u] = v;
            d[u] = d[v] + 1;
            init(u, v);
            ord.push_back({d[v], v});
        }
    }

    LCA(int root = 0) {
        int n = g.size();
        d.resize(n);
        fst.assign(n, -1);
        par.assign(n, -1);
        ord.clear();
        init(root);
        build(ord);
    }
};

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

    int n;
    cin >> n;
    vector<int> a(2 * n);
    for (int i = 0; i < 2 * n; ++i) {
        cin >> a[i];
        --a[i];
    }

    g.resize(2 * n);
    for (int i = 0; i < 2 * n - 1; ++i) {
        int v, u;
        cin >> v >> u;
        --v, --u;
        g[v].push_back(u);
        g[u].push_back(v);
    }

    vector<int> l(n, -1), r(n, -1);
    for (int i = 0; i < 2 * n; ++i) {
        if (l[a[i]] == -1) l[a[i]] = i;
        else r[a[i]] = i;
    }

    vector<char> ans(2 * n, 1);

    // 尝试两个可能的根（权值为 1 的节点）
    for (int root : {l[0], r[0]}) {
        LCA lca(root);
        vector<int> state(2 * n, 0); // 0:未定, 1:必须选, -1:禁止选

        // 标记必须选的节点（从 v 向上到根）
        auto mark = [&](int v) {
            while (v != -1 && state[v] != 1) {
                state[v] = 1;
                v = lca.par[v];
            }
        };

        // 标记禁止选（整个子树），并处理依赖
        auto markdel = [&](int v) {
            queue<int> q;
            q.push(v);
            state[v] = -1;
            while (!q.empty()) {
                int v = q.front();
                q.pop();
                // 另一个同权值的节点必须选
                mark(l[a[v]] ^ r[a[v]] ^ v);
                for (int u : g[v]) {
                    if (u != lca.par[v] && state[u] == 0) {
                        state[u] = -1;
                        q.push(u);
                    }
                }
            }
        };

        // 每个权值的 LCA 到根的路径必须选
        for (int i = 0; i < n; ++i) {
            mark(lca.lca(l[i], r[i]));
        }

        // 从大到小处理未确定的节点
        for (int i = 2 * n - 1; i >= 0; --i) {
            if (state[i] == 0) {
                markdel(i);
            }
        }

        // 收集当前解
        vector<char> cur(2 * n, 0);
        for (int i = 0; i < 2 * n; ++i) {
            if (state[i] == 1) cur[i] = 1;
        }

        // 反转后比较字典序（因为节点编号大的权重高）
        reverse(cur.begin(), cur.end());
        ans = min(ans, cur);
    }

    reverse(ans.begin(), ans.end());
    int cnt = count(ans.begin(), ans.end(), 1);
    cout << cnt << '\n';
    for (int i = 0; i < 2 * n; ++i) {
        if (ans[i]) cout << i + 1 << ' ';
    }
    cout << '\n';

    return 0;
}

复杂度分析

• 时间：$O(n \log n)$，LCA 预处理 $O(n \log n)$，标记函数均摊 $O(n)$
• 空间：$O(n)$

关键点总结

1. 代价 $2^i$ 的意义：等价于按节点编号降序的字典序最小化
2. 贪心选择：从大到小，能跳过就跳过
3. 根的选择：权值为 $1$ 的两个节点至少有一个必选
4. 连通性约束：选子节点必选父节点
5. 标记传播：禁止选整个子树，强制选另一个同权值节点
6. LCA 预处理：快速找到路径上的最低公共祖先