luogu P7737 [NOI2021] 庆典

本文主要是介绍luogu P7737 [NOI2021] 庆典，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面传送门
感觉写起来真吃屎一样的，变量名多的离谱。
首先这个是一个连通性问题那就先缩点。
然后考虑题目中的性质有啥用，也就是说一个点如果有两个入度，那么断掉其中一个对于答案没有影响。那么我们就得到一棵外向树。
问题来了，断掉哪一个。
考虑缩点的时候scc代表反向拓扑序，我们需要正向拓扑序最晚的保留，也就是反向拓扑序最早的，因此我们直接对于每个点保留scc最小的点就好了。
看到\(k\)这么小直接讨论啊，\(k=0\)判一下在不在子树内即可，\(k=1\)分走新增边和不走新增边讨论，\(k=2\)怎么这么难讨论啊。
然而这个\(k\leq 2\)是晃你的，实际上可以做到\(\sum\limits{k}\leq 10^5\)
将新增的边的两端点和起点和终点扔到树上建虚树，然后加上新的边直接跑暴力就好了。我们将每个点和每条链都建一条边，总点数和边数大概是\(9k\)的。
时间复杂度\(O((n+q)\log n)\)
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define ll long long
#define db double
#define lb long db
#define N (300000+5)
#define M (30000+5)
#define K (6)
#define mod 1000000007
#define Mod (mod-1)
#define eps (1e-9)
#define ull unsigned ll
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
#define R(n) (1ll*rand()*rand()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using namespace std;vector<int> S[N],G[50],T[50];queue<int> Qe;
int n,m,k,q,x,y,z,cnt,dh,fa[N][20],H,lg[N],d[N],dfn[N],Fa[50],low[N],scc[N],st[N],Ans,vis[N],sh,Q[N],Fs[N],Rt,W[50],B[50],F1[50],F2[50],T1[5],T2[5],Id[N],Ih;
I bool cmp(int x,int y){return dfn[x]<dfn[y];}I void Tarjan(int x){
	vis[x]=1;dfn[x]=low[x]=++dh;st[++H]=x;
	for(int i:S[x])dfn[i]?(vis[i]&&(low[x]=min(low[x],low[i]))):(Tarjan(i),low[x]=min(low[x],low[i]));
	if(dfn[x]==low[x]){++cnt;while(st[H+1]^x) scc[st[H]]=cnt,vis[st[H]]=0,Q[cnt]++,H--;}
}
I void Make(int x,int La){dfn[x]=++dh;fa[x][0]=La;d[x]=d[La]+1;Q[x]=Q[La]+Q[x];for(int i=1;fa[x][i-1];i++) fa[x][i]=fa[fa[x][i-1]][i-1];for(int i:S[x]) Make(i,x);}
I int LCA(int x,int y){d[x]<d[y]&&(swap(x,y),0);while(d[x]^d[y]) x=fa[x][lg[d[x]-d[y]]];if(x==y) return x;for(int i=lg[d[x]];~i;i--) fa[x][i]^fa[y][i]&&(x=fa[x][i],y=fa[y][i]);return fa[x][0];}
I void ADD(int x,int y){W[++Ih]=Q[fa[y][0]]-Q[x];G[Id[x]].PB(Ih);G[Ih].PB(Id[y]);} 
int main(){
	freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
	int i,j;scanf("%d%d%d%d",&n,&m,&q,&k);for(i=1;i<=m;i++) scanf("%d%d",&x,&y),S[x].PB(y);for(i=2;i<=n;i++) lg[i]=lg[i/2]+1;
	for(i=1;i<=n;i++) !dfn[i]&&(Tarjan(i),0); for(i=1;i<=n;i++) for(int j:S[i]) scc[i]^scc[j]&&(scc[i]<Fs[scc[j]]||!Fs[scc[j]])&&(Fs[scc[j]]=scc[i]);
	for(i=1;i<=n;i++) S[i].clear();for(i=1;i<=cnt;i++) Fs[i]?(S[Fs[i]].PB(i),0):(Rt=i);dh=0;Make(Rt,0);
	while(q--){
		scanf("%d%d",&x,&y);B[H=1]=Rt;B[++H]=x=scc[x];B[++H]=y=scc[y];for(i=1;i<=Ih;i++) W[i]=F1[i]=F2[i]=0,T[i].clear(),G[i].clear();
		for(i=1;i<=k;i++) scanf("%d%d",&T1[i],&T2[i]),B[++H]=T1[i]=scc[T1[i]],B[++H]=T2[i]=scc[T2[i]];sort(B+1,B+H+1,cmp);H=unique(B+1,B+H+1)-B-1;
		st[sh=1]=Rt;Ih=0;for(i=1;i<=H;i++) W[Id[B[i]]=++Ih]=Q[B[i]]-Q[fa[B[i]][0]];for(i=2;i<=H;i++){
			z=LCA(B[i],st[sh]);while(d[z]<=d[st[sh-1]]) ADD(st[sh-1],st[sh]),sh--;
			st[sh]^z&&(Id[z]=++Ih,W[Ih]=Q[z]-Q[fa[z][0]],ADD(z,st[sh]),st[sh]=z);st[++sh]=B[i];
		}while(sh^1) ADD(st[sh-1],st[sh]),sh--;
		for(i=1;i<=k;i++) G[Id[T1[i]]].PB(Id[T2[i]]);Qe.push(Id[x]);while(!Qe.empty()){z=Qe.front();Qe.pop();F1[z]=1;for(int i:G[z]) !F1[i]&&(Qe.push(i),0);}
		for(i=1;i<=Ih;i++) for(int j:G[i]) T[j].PB(i)/*,cerr<<i<<' '<<j<<'\n'*/;Qe.push(Id[y]);while(!Qe.empty()){z=Qe.front();Qe.pop();F2[z]=1;for(int i:T[z]) !F2[i]&&(Qe.push(i),0);}
		Ans=0;for(i=1;i<=Ih;i++) F1[i]&&F2[i]&&(Ans+=W[i]);printf("%d\n",Ans);
	}
}

这篇关于luogu P7737 [NOI2021] 庆典的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！