题解：P10304 [THUWC 2020] 道路修建

Havefunn · 2026-10-22 21:10:39 · 题解

题目

给定 n 个点 m 条边的 DAG。按优先访问最小编号相邻节点生成以 1 为根的 DFS 树。给定 q 个询问求若断开树上 a 到 b 路径的所有边，以 b 为根的子树中有多少个点无法从 1 到达。

思路

首先按照规则生成树，记录节点深度 dep 和 dfn，以及子树大小 siz 以及出栈逆序（即拓扑序）。

由于原图是 DAG，发现非树边只能是前向边或横叉边。定义 up_x 为仅断开一条树边时，节点 x 仍能从 1 到达的最高祖先深度最小值。

对于非树边 (y, x)，路径在 lca(x, y) 处分开，树上从 lca(x, y) 到 y 的路径中只要有一个点存活，即可救 x。所以按拓扑序递推，利用树上倍增维护路径 up 最小值：

然后将所有询问按被断开的最浅深度 dep_a 降序排序，离线。可以发现，随着深度递减，满足 up_x > dep_a 的节点会逐渐断联（可想为由黑变白）。

需要统计 b 子树内的断联点，利用并查集与树状数组维护区间状态：

• 连通块合并：节点 x 变白时，将其自身及下方的白块打包，利用并查集向上寻找第一个存活的黑点祖先 p。
• 树上差分：设上浮白块大小为 s，在树状数组中执行单点修改，即在 dfn_x 处加 s，dfn_p 处减 s。
• 区间查询：处理完当前深度的所有断联点后，询问 (a, b) 的答案即为树状数组中 b 子树的区间和，即 sum(dfn_b + siz_b - 1) - sum(dfn_b - 1)。

最后根据查询的 id 离线输出即可。

:::info[代码]

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int c,n,m,q;
vector<int>g[N],revg[N],buk[N];
int tim,ordtim;
int dfn[N],ord[N],dep[N],siz[N],f[N][25],ans[N];
int up[N],mi[N][25];
int bcj[N],tr[N],bsiz[N];
int find(int x){
    if(bcj[x]==x)
        return x;
    return bcj[x]=find(bcj[x]);
}
int lowbit(int x){
    return x&-x;
}
void add(int x,int y){
    for(int i=x;i<=n;i+=lowbit(i))
        tr[i]+=y;
}
int sum(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))
        res+=tr[i];
    return res;
}
void dfs(int x,int fa){
    dfn[x]=++tim;
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    siz[x]=1;
    for(int i=1;i<=19;i++)
        f[x][i]=f[f[x][i-1]][i-1];
    for(auto y:g[x]){
        if(!dfn[y]){
            dfs(y,x);
            siz[x]+=siz[y];
        }
    }
    ord[++ordtim]=x;
}
int lca(int x,int y){
    if(dep[x]<dep[y])
        swap(x,y);
    int k=dep[x]-dep[y];
    for(int i=19;i>=0;i--)
        if(k&(1<<i))
            x=f[x][i];
    if(x==y)
        return x;
    for(int i=19;i>=0;i--)
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];
}
int querymi(int nlca,int y){
    int res=up[nlca];
    int k=dep[y]-dep[nlca];
    for(int i=19;i>=0;i--)
        if(k&(1<<i)){
            res=min(res,mi[y][i]);
            y=f[y][i];
        }
    return res;
}
struct Que{
    int a,b,id;
};
vector<Que>que[N];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    //freopen("planet.in","r",stdin);
    //freopen("planet.out","w",stdout);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        revg[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        sort(g[i].begin(),g[i].end());
    dfs(1,0);
    for(int i=n;i>=1;i--){
        int x=ord[i];
        up[x]=dep[x];
        for(auto y:revg[x]){
            if(y==f[x][0])
                continue;
            up[x]=min(up[x],querymi(lca(y,x),y));
        }
        mi[x][0]=up[x];
        for(int k=1;k<=19;k++)
            mi[x][k]=min(mi[x][k-1],mi[f[x][k-1]][k-1]);
        buk[up[x]].push_back(x);
    }
    for(int i=1;i<=q;i++){
        int a,b;
        cin>>a>>b;
        que[dep[a]].push_back({a,b,i});
    }
    for(int i=1;i<=n;i++)
        bcj[i]=i;
    for(int d=n;d>=1;d--){
        for(auto x:buk[d+1]){
            int s=bsiz[x]+1;
            int p=find(f[x][0]);
            bsiz[p]+=s;
            add(dfn[x],s);
            if(p)
                add(dfn[p],-s);
            bcj[x]=f[x][0];
        }
        for(auto [a,b,id]:que[d])
            ans[id]=sum(dfn[b]+siz[b]-1)-sum(dfn[b]-1); 
    }
    for(int i=1;i<=q;i++)
        cout<<ans[i]<<'\n';
    return 0;
}

:::