CodeForces - 613D Kingdom and its Cities

传送门：CodeForces - 613D

思路分析

依然是构建虚树，然后再每棵虚树上进行贪心
设$num[x]$表示$x$的子树中未被隔断的点

1. 如果$x$是关键点，那么答案加上$num[x]$$(选择子树内关键点的父亲隔断)$，然后$num[x]=1$
2. 如果$x$不是关键点，且$num[x]>1$，$ans++$，$num[x]=0$

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N = 1e5+10;
#define int long long
vector<int>e[N];
int dep[N],f[N],top[N],son[N],siz[N],dfn[N],tim;

void dfs1(int u,int fa) {
    dep[u]=dep[fa]+1;
    siz[u]=1;
    son[u]=0;
    f[u]=fa;
    for(auto v:e[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 t) {
    top[u]=t;
    dfn[u]=++tim;
    if(!son[u]) return ;
    dfs2(son[u],t);
    for(auto v:e[u]) {
        if(v==f[u] || v==son[u]) continue;
        dfs2(v,v);
    }
}

int getlca(int x,int y) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    return x;
}

vector<int>new_e[N];
int st[N],Top;

void add(int u,int v){
    new_e[u].pb(v);
}

void insert(int x) {
    if(Top <= 1) {
        st[++Top] = x;
        return ;
    }
    int lca = getlca(x, st[Top]);
    if(lca == st[Top]) {
        st[++Top] = x;
        return;
    }
    while(Top > 1 && dfn[st[Top - 1]] >= dfn[lca]) {
        add(st[Top - 1], st[Top]);
        --Top;
    }
    if(lca != st[Top]) add(lca, st[Top]), st[Top] = lca;
    st[++Top] = x;
}

int dp[N],vis[N],num[N];

int dfs(int u){
    int ans=0;
    for(auto v:new_e[u]){
        ans+=dfs(v);
        num[u]+=num[v];
    }
    if(vis[u]){
        ans+=num[u];
        num[u]=1;
    }else{
        if(num[u]>1){
            ans++;
            num[u]=0;
        }
    }
    return ans;
}

void del(int u){
    num[u]=0;
    vis[u]=0;
    for(auto v:new_e[u]) del(v);
    new_e[u].clear();
}

signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int n,q;
    read(n);
    for(int i=1; i<n; i++) {
        int u,v;
        read(u,v);
        e[u].pb(v);
        e[v].pb(u);
    }
    dfs1(1,0);
    dfs2(1,1);
    read(q);
    while(q--) {
        int m;
        vector<int>tmp;
        read(m);
        for(int i=1; i<=m; i++) {
            int x;
            read(x);
            vis[x]=1;
            tmp.pb(x);
        }
        sort(all(tmp),[](int x,int y) {
            return dfn[x]<dfn[y];
        });
        
        int flag=0;
        for(auto i:tmp) if(vis[f[i]]) flag=1;
        if(flag){
            for(auto i:tmp) vis[i]=0;
            puts("-1");
            continue;
        }
        
        Top=0;
        if(!vis[1]) st[++Top]=1;
        for(auto i:tmp) insert(i);
        while(Top>1){
            add(st[Top-1],st[Top]);
            --Top;
        }
        
        printf("%d\n",dfs(1));
        del(1);

    }




    return 0;
}