P9340

Mikefeng · 2023-05-30 20:17:47 · 题解

前言：看到杨老师的 O(n\log^2 n) 做法，所以来写一个 O(n\sqrt n) 做法。

题意

多次查询包含区间中所有点的连通块最小大小。

做法

区间查询，可以离线，一眼鉴定为莫队。

包含所有关键点的连通块最小大小是经典问题，虚树中边的数量等于按 dfs 排序后两两相邻的点的距离之和。（第一个和最后一个也相邻）

这样就获得了 O(n\sqrt n\log n) 的做法，直接莫队，记录每个点的出现数量，如果删到了 0 就从点集中去掉，用 set 动态维护前驱后继，同时维护虚树大小。

因为懒得写回滚莫队，先写了 set，有 28 分的高分。

发现只删的前驱后继可以用链表维护，套一个只删不加的回滚莫队，右端点从右到左排序，同时用 O(1) lca 求两个点间的距离，用的是 dfs 序 lca，这样常数小，还不用多记一个欧拉序。

时间复杂度 O(n\sqrt n)。

代码

const int N=1e5+5;
int n,m,k,len,res;
int a[N],ans[N];
int num[N],lg[N];
vector<int> e[N];
int id[N],rk[N],dep[N];
int st[20][N],cnt;
inline void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    id[u]=++cnt;rk[cnt]=u;
    st[0][cnt]=fa;
    for(int v:e[u]) if(v!=fa) dfs(v,u);
}
inline int Min(int x,int y){return dep[x]<dep[y]?x:y;}
inline void init(){
    F(i,2,n) lg[i]=lg[i>>1]+1;
    F(j,1,19) F(i,1,cnt-(1<<j)+1) st[j][i]=Min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
inline int lca(int l,int r){
    if(l==r) return rk[l];
    if(l>r) swap(l,r);
    ++l;int k=lg[r-l+1];
    return Min(st[k][l],st[k][r-(1<<k)+1]);
}
inline int dis(int x,int y){return dep[rk[x]]+dep[rk[y]]-2*dep[lca(x,y)];}
struct md{
    int l,r,bid,id;
    inline bool operator < (const md &x)const{return bid!=x.bid?l<x.l:r>x.r;}
}q[N];
int pre[N],nxt[N];
struct node{
    int pre,nxt,id;
    node(){}
    node(int pre,int nxt,int id):pre(pre),nxt(nxt),id(id){}
};
vector<node> s;
inline void Del(int x){
    --num[x];
    if(!num[x]){
        res-=dis(pre[x],x)+dis(x,nxt[x]);
        res+=dis(pre[x],nxt[x]);
        pre[nxt[x]]=pre[x];nxt[pre[x]]=nxt[x];
    }
}
inline void del(int x){
    s.emplace_back(pre[x],nxt[x],x);
    --num[x];
    if(!num[x]){
        res-=dis(pre[x],x)+dis(x,nxt[x]);
        res+=dis(pre[x],nxt[x]);
        pre[nxt[x]]=pre[x];nxt[pre[x]]=nxt[x];
    }
}
inline void solve(){
    int l=1,r=0;
    F(i,1,m){
        if(q[i].bid!=q[i-1].bid){
            memset(num,0,sizeof num);
            F(j,(q[i].bid-1)*len+1,k) ++num[id[a[j]]];
            int lst=0;F(j,1,n){
                pre[j]=lst;
                if(num[j]) lst=j;
            }
            F(j,1,n) if(!pre[j]) pre[j]=lst;
            lst=0;UF(j,n,1){
                nxt[j]=lst;
                if(num[j]) lst=j;
            }
            UF(j,n,1) if(!nxt[j]) nxt[j]=lst;
            res=0;
            F(j,1,n) if(num[j]) res+=dis(pre[j],j);
            r=k;
        }
        l=(q[i].bid-1)*len+1;
        while(r>q[i].r) Del(id[a[r--]]);
        int now=res;
        while(l<q[i].l) del(id[a[l++]]);
        ans[q[i].id]=res/2+1;
        res=now;
        while(!s.empty()){
            node tmp=s.back();s.pop_back();
            if(!num[tmp.id]) nxt[tmp.pre]=tmp.id,pre[tmp.nxt]=tmp.id;
            ++num[tmp.id];
        }
    }
}
bool M2;
int main(){
    int Time=clock();
    look_memory;
    n=read();k=read();m=read();
    len=sqrt(k);
    F(i,1,n-1){
        int u=read(),v=read();
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    dfs(1,0);init();
    F(i,1,k) a[i]=read();
    F(i,1,m) q[i].l=read(),q[i].r=read(),q[i].bid=(q[i].l-1)/len+1,q[i].id=i;
    sort(q+1,q+m+1);
    solve();
    F(i,1,m) cout<<ans[i]<<'\n';
    look_time;
    return 0;
}