CF613D Kingdom and its Cities（虚树）

通过领悟题意，发现本题只与关键点和他们的lca有关，因此把只需要对他们建虚树

对于dp思路，如果x不是关键点，那么观察子树中有多少需要断开的，如果超过1，那么直接断开这个点，如果等于1，先保留看看能否与后面的一起。

如果是关键点，那就必须要把当前点和子树中的所有关键点断开，首先我们知道一定存在合法方案，因为不存在的已经特判过了，所以只需记录子树中的个数即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e5+10;
const int mod=998244353;
vector<int> g1[N],g[N];
int dfn[N],times,f[N][25],st[N],depth[N];
int cnt[N],q[N],d[N],sign[N];
int vis[N];
void dfs(int u,int fa){
    depth[u]=depth[fa]+1;
    dfn[u]=++times;
    int i;
    f[u][0]=fa;
    for(i=1;i<=21;i++){
        f[u][i]=f[f[u][i-1]][i-1];
    }
    for(i=0;i<g1[u].size();i++){
        int v=g1[u][i];
        if(v==fa)
            continue;
        dfs(v,u);
    }
}
bool cmp(int x,int y){
    return dfn[x]<dfn[y];
}
int lca(int a,int b){
    if(depth[a]<depth[b])
        swap(a,b);
    int i;
    for(i=21;i>=0;i--){
        if(depth[f[a][i]]>=depth[b]){
            a=f[a][i];
        }
    }
    if(a==b)
        return a;
    for(i=21;i>=0;i--){
        if(f[a][i]!=f[b][i]){
            a=f[a][i];
            b=f[b][i];
        }
    }
    return f[a][0];
}
void add(int a,int b){
    g[a].push_back(b);
}
void get(int u){
    int i;
    int cnt=0;
    for(i=0;i<g[u].size();i++){
        int v=g[u][i];
        get(v);
        d[u]+=d[v];
        if(st[u]){
            d[u]+=sign[v];
        }
        else{
            if(sign[v])
                cnt++;
        }
        d[v]=0,st[v]=0,sign[v]=0,vis[v]=0;
    }
    if(!st[u]){
        if(cnt>1){
            d[u]++;
        }
        else if(cnt==1){
            sign[u]=1;
        }
    }
    g[u].clear();
}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    int i;
    for(i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        g1[a].push_back(b);
        g1[b].push_back(a);
    }
    dfs(1,0);
    int t;
    cin>>t;
    while(t--){
        int k;
        cin>>k;
        for(i=1;i<=k;i++){
            int x;
            cin>>x;
            st[x]=1;
            cnt[i]=x;
            sign[x]=1;
            vis[x]=1;
        }
        int kk=0;
        for(i=1;i<=k;i++){
            if(vis[f[cnt[i]][0]]){
                kk=1;
                break;
            }
        }
        if(kk){
            for(i=1;i<=k;i++){
                vis[cnt[i]]=0;
                sign[cnt[i]]=0;
                st[cnt[i]]=0;
            }
            cout<<-1<<endl;
            continue;
        }
        sort(cnt+1,cnt+1+k,cmp);
        q[1]=1;
        int tt=1;
        for(i=1;i<=k;i++){
            if(cnt[i]==1)
                continue;
            int p=lca(cnt[i],q[tt]);
            if(p!=q[tt]){
                while(dfn[p]<dfn[q[tt-1]]){
                    add(q[tt-1],q[tt]);
                    tt--;
                }
                if(dfn[p]!=dfn[q[tt-1]]){
                    add(p,q[tt]);
                    q[tt]=p;
                }
                else{
                    add(p,q[tt]);
                    tt--;
                }
            }
            q[++tt]=cnt[i];
        }
        for(i=1;i<tt;i++){
            add(q[i],q[i+1]);
        }
        get(1);
        cout<<d[1]<<endl;
        d[1]=0,sign[1]=0,st[1]=0,vis[1]=0;
    }
    return 0;
}

View Code

CF613D Kingdom and its Cities（虚树）

相关推荐