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

· · 题解

删掉 a 到 b 的树边后，如果要从 1 到达 b 子树中的点 u，要么通过非树边直接到达 u，要么通过非树边到达 u 的祖先后再沿着树边走到 u。

我们先只考虑第一种情况，显然，可达性具有单调性，只有 a 的深度大于某个值，才可以到达，我们设这个值为 f_u。

假设我们已经求出来 f，一个点可以到达当且仅当它到 b 的路径上有一个点的 f 小于等于 dep_a。可以把询问离线下来，挂在 b 点上，对路径上 f 的最大值建立权值线段树，用线段树合并来求。当前遍历到点 b 时，先把它的所有子树合并起来，然后加入 f_b，将所有大于 f_b 的值修改为 f_b 即可，答案是大于 dep_a 的数量。

那么现在的问题就是如何求出 f，可以按照拓扑序倒序遍历整个 dag，如果现在有一条非树边 u\to v，加入后，f_v 可以对于 lca_{u,v} 到 u 上的 f 取最小值，倍增处理即可。

这道题的数据似乎有一些问题，有一个点会出现重边和无法到达的点，要注意一下。

:::info[参考代码]


#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,inf=1e9;
int n,m,q,cnt,fa[N][20],dep[N],d[N],f[N],g[N][20],ans[N],root[N];
vector<pair<int,bool>>ch[N];
bool vis[N];
struct ask{
    int a,id;
};
vector<ask>v[N];
struct tree{
    int val,ls,rs,tag;
}tr[N*30];
void dfs(int x){
    vis[x]=1;
    dep[x]=dep[fa[x][0]]+1;
    for(int i=1;i<20;i++){
        fa[x][i]=fa[fa[x][i-1]][i-1];
    }
    for(int i=0;i<ch[x].size();i++){
        int v=ch[x][i].first;
        if(vis[v]){
            continue;
        }
        ch[x][i].second=1;
        fa[v][0]=x;
        dfs(v);
    }
}
int lca(int x,int y){
    if(dep[x]<dep[y]){
        swap(x,y);
    }
    for(int i=19;i>=0;i--){
        if(dep[fa[x][i]]>=dep[y]){
            x=fa[x][i];
        }
    }
    if(x==y){
        return x;
    }
    for(int i=19;i>=0;i--){
        if(fa[x][i]!=fa[y][i]){
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    return fa[x][0];
}
int find(int x,int y){
    int mi=f[x];
    for(int i=19;i>=0;i--){
        if(dep[fa[x][i]]>=dep[y]){
            mi=min(mi,g[x][i]);
            x=fa[x][i];
        }
    }
    return mi;
}
void topu(){
    queue<int>q;
    f[0]=inf;
    for(int i=0;i<20;i++){
        g[0][i]=inf;
    }
    for(int i=1;i<=n;i++){
        f[i]=dep[i];
    }
    q.push(1);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        g[x][0]=f[fa[x][0]];
        for(int i=1;i<20;i++){
            g[x][i]=min(g[x][i-1],g[fa[x][i-1]][i-1]);
        }
        for(int i=0;i<ch[x].size();i++){
            int v=ch[x][i].first;
            if(!ch[x][i].second){
                f[v]=min(f[v],find(x,lca(x,v)));
            }
            d[v]--;
            if(!d[v]){
                q.push(v);
            }
        } 
    }
}
void pushdown(int x){
    if(tr[x].tag){
        tr[tr[x].ls].val=tr[tr[x].rs].val=0;
        tr[tr[x].ls].tag=tr[tr[x].rs].tag=1;
        tr[x].tag=0;
    }
}
void pushup(int x){
    tr[x].val=tr[tr[x].ls].val+tr[tr[x].rs].val;
}
void clear(int x,int l,int r,int L,int R){
    if(L>R||!x){
        return;
    }
    if(L<=l&&r<=R){
        tr[x].val=0;
        tr[x].tag=1;
        return;
    }
    pushdown(x);
    int mid=(l+r)/2;
    if(L<=mid){
        clear(tr[x].ls,l,mid,L,R);
    }
    if(mid<R){
        clear(tr[x].rs,mid+1,r,L,R);
    }
    pushup(x);
}
void modify(int &x,int l,int r,int s,int k){
    if(!x){
        x=++cnt;
    }
    if(l==r){
        tr[x].val+=k;
        return;
    }
    pushdown(x);
    int mid=(l+r)/2;
    if(s<=mid){
        modify(tr[x].ls,l,mid,s,k);
    }
    else{
        modify(tr[x].rs,mid+1,r,s,k);
    }
    pushup(x);
}
int query(int x,int l,int r,int L,int R){
    if(L>R||!x){
        return 0;
    }
    if(L<=l&&r<=R){
        return tr[x].val;
    }
    pushdown(x);
    int mid=(l+r)/2,sum=0;
    if(L<=mid){
        sum+=query(tr[x].ls,l,mid,L,R);
    }
    if(mid<R){
        sum+=query(tr[x].rs,mid+1,r,L,R);
    }
    return sum;
}
void merge(int &x,int y,int l,int r){
    if(!x||!y){
        x=x+y;
        return;
    }
    if(l==r){
        tr[x].val+=tr[y].val;
        return;
    }
    pushdown(x);
    pushdown(y);
    int mid=(l+r)/2;
    merge(tr[x].ls,tr[y].ls,l,mid);
    merge(tr[x].rs,tr[y].rs,mid+1,r);
    pushup(x);
}
void solve(int x){
    for(int i=0;i<ch[x].size();i++){
        if(!ch[x][i].second){
            continue;
        }
        int v=ch[x][i].first;
        solve(v);
        merge(root[x],root[v],0,n);
    }
    int s=query(root[x],0,n,f[x]+1,n)+1;
    clear(root[x],0,n,f[x]+1,n);
    modify(root[x],0,n,f[x],s);
    for(int i=0;i<v[x].size();i++){
        ans[v[x][i].id]=query(root[x],0,n,dep[v[x][i].a]+1,n);
    }
}
int main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        ch[u].push_back({v,0});
        d[v]++;
    }
    for(int i=1;i<=q;i++){
        int a,b;
        cin>>a>>b;
        v[b].push_back({a,i});
    }
    for(int i=1;i<=n;i++){
        sort(ch[i].begin(),ch[i].end());
    }
    dfs(1);
    topu();
    solve(1);
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}
:::