[Easy-Medium] CF2042E Vertex Pairs

xiezheyuan2025/1/29约 1000 字大约 5 分钟

简要题意

给定一个 $2n$ 个点的树，点有点权，点权位于 $[1,n]$ 且对于每一个 $x\in[1,n]$ ，都恰好存在两个点点权为 $x$ ，选择点 $i$ 的代价为 $2^i$ 。

你需要选择一个连通块，使得选择的点覆盖了所有点权且代价总和最小，输出选取的方案。

$1\leq n\leq 2\times 10^5$ 。

思路

看到题目，唯一的切入点应该就是覆盖了所有点权了，那么自然得到对于两个同点权的点 $x,y$ ，至少有一个在答案中。不过好像没什么用？不不不，盲生，你发现了华点。

不妨钦定一个点必须在答案中，那么不妨以这个点为根，则我们不选择一个点，则它的子树的所有点都无法选择，这是一个关键性质。

看到代价的形式，不难想到从大到小枚举点去做经典按位贪心，如果这个点可以不出现在答案中，那么不出现在答案中一定最优。

现在的问题是如何判断一个点必须出现在答案中，那么要么这个点的子树中存在两个同点权点，要么存在一个点，使得与其同点权的点无法选择。

对于第一种情况，只需要预先标记同点权的点 $x,y$ 的 LCA 到根的路径均必须选择即可。

对于第二种情况，我们在决定不选择一个点时，暴力向下 dfs，找到这个点的同色点，它到根的路径均必须选择。注意需要保证每个点只会向下 dfs 一次。

然后需要考虑我们用什么数据结构来维护，由于若一个点必须选择，则其祖先均必须选择，所以可以直接暴力更改就好了，无需重链剖分。

时间复杂度 $O(n\log n)$ 可以通过本题，将 LCA 算法换成 $O(1)$ RMQ 可以做到 $O(n)$ 。

代码

感觉这个做法题解区已经有一片了，但好像大家都没有放代码，那我就补充一下我的实现吧。

#include <bits/stdc++.h>
#define ls (i << 1)
#define rs (i << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;

const int N = 4e5 + 5;
int n, a[N], rt;
vector<int> b[N], g[N];

int father[N], dep[N], siz[N], son[N], top[N], dfn[N], rev[N];

void dfs1(int u, int fa){
    dep[u] = dep[fa] + 1, father[u] = fa, siz[u] = 1;
    for(int v : g[u]){
        if(v == fa) continue;
        dfs1(v, u), siz[u] += siz[v];
        if(siz[v] > siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int fa){
    dfn[u] = ++dfn[0], rev[dfn[u]] = u;
    if(son[u]) top[son[u]] = top[u], dfs2(son[u], u);
    for(int v : g[u]){
        if(v == fa || v == son[u]) continue;
        top[v] = v, dfs2(v, u);
    }
}

bool val[N];

void update(int x){
    for(;x&&!val[x];x=father[x]) val[x] = true;
}

bool ret[2][N], removed[N];

int lca(int x, int y){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        x = father[top[x]];
    }
    return dep[x] < dep[y] ? x : y;
}

void solve(bool ret[]){
    top[rt] = rt, dfn[0] = father[rt] = 0;
    dfs1(rt, 0), dfs2(rt, 0);
    for(int i=1;i<=(n>>1);i++) update(lca(b[i][0], b[i][1]));
    update(rt);
    for(int i=n;i;i--){
        if(val[i]) ret[i] = true;
        else{
            int j = dfn[i];
            for(;j<=dfn[i]+siz[i]-1;j++){
                if(removed[j]){
                    j = j + siz[rev[j]] - 1;
                    continue;
                }
                removed[j] = true;
                int t = a[rev[j]];
                update(rev[j] == b[t][0] ? b[t][1] : b[t][0]);
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n; n <<= 1;
    for(int i=1;i<=n;i++) cin >> a[i], b[a[i]].push_back(i);
    for(int i=1,u,v;i<n;i++){
        cin >> u >> v;
        g[u].push_back(v), g[v].push_back(u);
    }
    rt = b[1][0], solve(ret[0]);
    fill(son + 1, son + n + 1, 0);
    fill(val + 1, val + n + 1, false);
    fill(removed + 1, removed + n + 1, false);
    rt = b[1][1], solve(ret[1]);
    bool result = 0;
    for(int i=n;i;i--){
        if(ret[0][i] != ret[1][i]){
            result = ret[0][i] ? 1 : 0;
            break;
        }
    }
    cout << count(ret[result] + 1, ret[result] + n + 1, 1) << '\n';
    for(int i=1;i<=n;i++){
        if(ret[result][i]) cout << i << ' ';
    }
    cout << '\n';
    return 0;
}

// Written by xiezheyuan