题解归档 - cf613D

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf613D
• 本地来源：problems/cf613D/idea.md
• 题目链接：https://codeforces.com/contest/613/problem/D
• 原始标题：CF613D Kingdom and its Cities（虚树）

思路

CF613D Kingdom and its Cities（虚树）

题意

树上每次询问给定若干「重要城市」。只能删除非重要城市，求使重要城市两两不连通的最少删除数；若存在相邻重要城市则输出 -1。

做法

1. 根定为 1，倍增 LCA + dfn 排序。
2. 不合法：存在重要点其父也是重要点（等价于树上有相邻重要点）。
3. 虚树：关键点按 dfn 排序，insert 栈建树；弹栈时连边，边方向取深度浅者为父。

4. 虚树 DP（lhm 写法）：

   • 重要点 x：对每个子 y 若 num[y]>0 则 ans++（或仅对重要子点计数，实现中待统一）。
   • 非重要点：统计有「重要信息」的子树个数 cnt；cnt>1 则 ans++；cnt==1 把子信息上推。
5. 多测清空虚树 head 与 num（只清 tmp 记录点）。

实现注意

• dfs 必须用局部循环变量，全局 i 递归会破坏遍历（曾导致本地 TLE）。
• 虚树连边避免 u==v；父深度应严格小于子深度。
• -1 判定要在全部重要点标记完成后再查父亲。

状态

• 官方样例 Q1/Q2/Q4 通过；Q3 本地仍为 2（期望 1），对拍未全过，暂不入队提交。

参考

• CF Round #339 Editorial
• 虚树 + 树 DP 经典写法

代码

来源：problems/cf613D/solution.cpp

/* Author: likely
 * Time: 2026-06-08 02:41:30
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=100005,lg=17;
ll n,q,i,j,k,m,top,ans,pd,cur,dq,tim,ecnt,tmp_cnt;
ll f[maxn+5][20],dep[maxn+5],dfn[maxn+5],num[maxn+5],imp[maxn+5],head[maxn+5];
ll a[maxn+5],stk[maxn+5],tmp[maxn+5];
vector<ll>ss[maxn+5];
struct edge{
    ll to,nxt;
}e[maxn*4+5];
bool cmp(ll x,ll y){
    return dfn[x]<dfn[y];
}
void add_e(ll u,ll v){
    if(u==v) return;
    if(dep[u]>dep[v]) swap(u,v);
    e[++ecnt]={v,head[u]},head[u]=ecnt;
}
void dfs(ll x,ll fa){
    ll ii,zc;
    dfn[x]=++tim,dep[x]=dep[fa]+1,f[x][0]=fa;
    for(ii=1;ii<=lg;ii++) f[x][ii]=f[f[x][ii-1]][ii-1];
    for(ii=0;ii<(ll)ss[x].size();ii++){
        zc=ss[x][ii];
        if(zc!=fa) dfs(zc,x);
    }
}
ll LCA(ll x,ll y){
    ll ii;
    if(dep[x]<dep[y]) swap(x,y);
    for(ii=lg;ii>=0;ii--) if(dep[f[x][ii]]>=dep[y]) x=f[x][ii];
    if(x==y) return x;
    for(ii=lg;ii>=0;ii--) if(f[x][ii]!=f[y][ii]) x=f[x][ii],y=f[y][ii];
    return f[x][0];
}
void ins(ll x){
    if(x==1) return;
    if(top==1){
        stk[++top]=x;
        return;
    }
    cur=LCA(x,stk[top]);
    if(cur==stk[top]){
        stk[++top]=x;
        return;
    }
    while(top>1 and dfn[cur]<=dfn[stk[top-1]]){
        add_e(stk[top-1],stk[top]);
        top--;
        tmp[++tmp_cnt]=stk[top];
    }
    if(cur!=stk[top]){
        add_e(cur,stk[top]);
        stk[top]=cur;
        tmp[++tmp_cnt]=cur;
    }
    stk[++top]=x;
}
void dp_vt(ll x){
    ll zc,sum,ii;
    zc=0,sum=0;
    for(ii=head[x];ii;ii=e[ii].nxt){
        dq=e[ii].to;
        dp_vt(dq);
        if(imp[x] and imp[dq]) ans++;
        if(!imp[x] and num[dq]){
            zc++;
            sum+=num[dq];
        }
    }
    if(!imp[x]){
        if(zc==1) num[x]+=sum;
        if(zc>1) ans++;
    }
    head[x]=0;
}
int main(){
    cin>>n;
    for(i=1;i<n;i++){
        cin>>j>>k;
        ss[j].push_back(k),ss[k].push_back(j);
    }
    dfs(1,0);
    cin>>q;
    while(q--){
        cin>>m;
        ecnt=tmp_cnt=ans=pd=0;
        for(i=1;i<=m;i++){
            cin>>a[i];
            imp[a[i]]=1;
            num[a[i]]=1;
        }
        for(i=1;i<=n;i++) if(imp[i] and imp[f[i][0]]) pd=1;
        if(pd){
            cout<<"-1\n";
            for(i=1;i<=m;i++) imp[a[i]]=0,num[a[i]]=0;
            continue;
        }
        sort(a+1,a+m+1,cmp);
        top=1,stk[1]=1,tmp[++tmp_cnt]=1;
        for(i=1;i<=m;i++) ins(a[i]);
        while(top>1){
            add_e(stk[top-1],stk[top]);
            top--;
            tmp[++tmp_cnt]=stk[top];
        }
        dp_vt(1);
        cout<<ans<<"\n";
        for(i=1;i<=tmp_cnt;i++) head[tmp[i]]=0,num[tmp[i]]=0;
        for(i=1;i<=m;i++) imp[a[i]]=0;
    }
    return 0;
}