Codeforces 613D Kingdom and its Cities

https://codeforces.com/problemset/problem/613/D

题意：给一棵树，m次询问，询问k个点，至少需要在树上去掉多少个点使得这k个点都不联通。\(sumk \le 1e5, n \le 1e5, q \le 1e5\)

题解：

显然的一个贪心是，对于割边相连的两个点，取任意一个割断开都是合理的，否则两个点应该在与其他点有连边的交叉点隔开，这样不仅两个点隔开了，两个点也能与外面的点隔开。而如果两个点紧邻又都是关键点显然就无解。

那么首先来考虑单次询问，直接考虑定根，这里显然发现非割边相连点的那种解在任意根都是取lca处。所以考虑树dp。如果 \(a_i\) 表示 \(i\) 号点是否需要取，\(dp_i\) 表示 \(i\) 这颗子树是否有需要隔开的点，\((u,v)\) 表示父亲和儿子，首先处理紧邻点，如果 \(a_v=a_u=1\) 则直接输出 -1。再考虑如果 \(a_u=1, dp_v=1\) 则说明出现一个割边相连点，直接把答案+1，如果存在多个 \(dp_{v}=1\)，则需要把父节点删掉。再最后更新 \(dp_u\) 的值，如果 \(u\) 没有被删且子树内存在关键点就是1，否则是0。

再考虑多次询问。由于询问独立，可以考虑用虚树做，套上单次询问的 dp 即可。

更简单的写法是启发式合并，用 set 维护一个 \(res_i\) 表示 \(i\) 这颗子树有哪些次询问的 \(dp_i=1\) 即可。

代码（set 启发式合并）：

/*================================================================
*
*   创 建 者： badcw
*   创建日期： 2020/6/16 21:20
*
================================================================*/
#include <bits/stdc++.h>

#define ll long long
using namespace std;

const int maxn = 1e5+50;
const int mod = 1e9+7;
ll qp(ll a, ll n, ll mod = ::mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int n;
vector<int> edge[maxn];
set<int> query[maxn];
set<int> res[maxn];
int ans[maxn];

void del(int pos) { ans[pos] = -1; }
void add(int pos) { if (ans[pos] != -1) ans[pos] ++; }

void dfs(int u, int fa) {
    set<int> lca;
    res[u] = query[u];
    for (auto v : edge[u]) {
        if (v == fa) continue;
        for (auto i : query[v]) {
            if (query[u].count(i)) del(i);
        }
        dfs(v, u);
        if (res[v].size() > res[u].size()) swap(res[v], res[u]);
        for (auto q : res[v]) {
            if (query[u].count(q)) add(q);
            else if (res[u].count(q)) lca.insert(q);
            else res[u].insert(q);
        }
    }
    for (auto q : lca) {
        res[u].erase(q);
        add(q);
    }
}

int main(int argc, char* argv[]) {
    scanf("%d", &n);
    for (int i = 1; i < n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        edge[u].push_back(v), edge[v].push_back(u);
    }
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; ++i) {
        int num;
        scanf("%d", &num);
        while (num --) {
            int x;
            scanf("%d", &x);
            query[x].insert(i);
        }
    }
    dfs(1, 0);
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}

Codeforces 613D Kingdom and its Cities

原文：https://www.cnblogs.com/badcw/p/13152293.html