P10304 题解

· · 题解

Problem Link

题目大意

给定一张 n 个点 m 条边的 DAG，求出以 1 为根的 dfs 生成树 T，q 次询问给定 a,b，其中 a 在 T 中是 b 的祖先，查询若删 a\to b 在 T 上路径的边后，b 在 T 上的子树中有多少个点不能从 1 出发到达。

数据范围：n,q\le 10^5,m\le 1.5\times 10^5。

思路分析

先考虑 b 是否可达，这个事情显然对 a 的深度有单调性，因此我们求出 f_b 表示如果存在 1\to b 路径，dep_a 至少是多少。

初始 f_b=dep_b，转移时逆拓扑序考虑每条非树边，对于非树边 u\to v，那么就会把 f_v 用 u\to\mathrm{LCA}(u,v) 路径上最小的 f 更新，可以倍增维护。

然后考虑 b 子树内的某个点 c，容易发现 c 能到达的条件就是 b\to c 路径上存在一个 f_u\le dep_a。

离线下来维护 v 到当前节点 u 的路径最小 f，更新就是求出 (f_u,n] 内的节点数加到 f_u 上并清空 (f_u,n]，查询就是后缀求和，不难用值域线段树合并维护。

时间复杂度 \mathcal O((n+m+q)\log n)。

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,m,dep[MAXN],dfn[MAXN],dcnt,st[MAXN][20],deg[MAXN],up[MAXN][20];
vector <int> G[MAXN],E[MAXN],ord,O[MAXN];
void dfs0(int u,int fz) {
    dep[u]=dep[fz]+1,dfn[u]=++dcnt,st[dcnt][0]=fz,up[u][0]=fz;
    for(int k=1;k<20;++k) up[u][k]=up[up[u][k-1]][k-1];
    for(int v:G[u]) {
        if(!dfn[v]) E[u].push_back(v),dfs0(v,u);
        else O[u].push_back(v);
    }
}
int bit(int x) { return 1<<x; }
int cmp(int x,int y) { return dfn[x]<dfn[y]?x:y; }
int LCA(int x,int y) {
    if(x==y) return x;
    int l=min(dfn[x],dfn[y])+1,r=max(dfn[x],dfn[y]),k=__lg(r-l+1);
    return cmp(st[l][k],st[r-bit(k)+1][k]);
}
int f[MAXN],mn[MAXN][20];
int qry(int x,int r) {
    int s=f[r];
    for(int k=19;~k;--k) if(dep[up[x][k]]>=dep[r]) s=min(s,mn[x][k]),x=up[x][k];
    return s;
}
struct SegmentTree {
    int tot,tr[MAXN*20],ls[MAXN*20],rs[MAXN*20];
    void ins(int u,int x,int l,int r,int &p) {
        if(!p) p=++tot;
        tr[p]+=x;
        if(l==r) return ;
        int mid=(l+r)>>1;
        u<=mid?ins(u,x,l,mid,ls[p]):ins(u,x,mid+1,r,rs[p]);
    }
    void merge(int l,int r,int q,int &p) {
        if(!q||!p) return p|=q,void();
        tr[p]+=tr[q];
        if(l==r) return ;
        int mid=(l+r)>>1;
        merge(l,mid,ls[q],ls[p]),merge(mid+1,r,rs[q],rs[p]);
    }
    int qry(int ul,int ur,int l,int r,int p) {
        if(ul<=l&&r<=ur) return tr[p];
        int mid=(l+r)>>1,s=0;
        if(ul<=mid) s+=qry(ul,ur,l,mid,ls[p]);
        if(mid<ur) s+=qry(ul,ur,mid+1,r,rs[p]);
        return s;
    }
    void del(int ul,int ur,int l,int r,int &p) {
        if(ul<=l&&r<=ur) return tr[p]=0,p=0,void();
        int mid=(l+r)>>1;
        if(ul<=mid) del(ul,ur,l,mid,ls[p]);
        if(mid<ur) del(ul,ur,mid+1,r,rs[p]);
        tr[p]=tr[ls[p]]+tr[rs[p]];
    }
}   T;
int rt[MAXN],ans[MAXN];
vector <array<int,2>> qys[MAXN];
void dfs1(int u) {
    T.ins(f[u],1,1,n,rt[u]);
    for(int v:E[u]) dfs1(v),T.merge(1,n,rt[v],rt[u]);
    if(f[u]<n) {
        int w=T.qry(f[u]+1,n,1,n,rt[u]);
        T.ins(f[u],w,1,n,rt[u]),T.del(f[u]+1,n,1,n,rt[u]);
    }
    for(auto z:qys[u]) if(z[0]<n) ans[z[1]]=T.qry(z[0]+1,n,1,n,rt[u]);
}
signed main() {
    int q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),G[u].push_back(v),++deg[v];
    for(int i=1;i<=n;++i) sort(G[i].begin(),G[i].end());
    queue <int> Q;
    for(int i=1;i<=n;++i) if(!deg[i]) Q.push(i);
    while(Q.size()) {
        int u=Q.front(); Q.pop(),ord.push_back(u);
        for(int v:G[u]) if(!--deg[v]) Q.push(v);
    }
    dfs0(1,0);
    for(int k=1;k<20;++k) for(int i=1;i+bit(k)-1<=dcnt;++i) {
        st[i][k]=cmp(st[i][k-1],st[i+bit(k-1)][k-1]);
    }
    for(int i=1;i<=n;++i) if(dfn[i]) f[i]=dep[i];
    for(int u:ord) if(dfn[u]) {
        mn[u][0]=f[u];
        for(int k=1;k<20;++k) mn[u][k]=min(mn[u][k-1],mn[up[u][k-1]][k-1]);
        for(int v:O[u]) if(dfn[v]) f[v]=min(f[v],qry(u,LCA(u,v)));
    }
    for(int i=1,a,b;i<=q;++i) scanf("%d%d",&a,&b),qys[b].push_back({dep[a],i});
    dfs1(1);
    for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
    return 0;
}