自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 22:56:45，当前版本为作者最后更新于2024-09-22 16:43:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}