Statement

题目大意

给定一棵基环外向树，和若干组询问，对于每次独立的询问都指定一些起点和一些终点，你删去一些边，使得从任意起点出发都无法到达终点，并让删去的边的编号的最小值最大，求这个最大的最小值。

题解

不难发现，在基环外向树中，任意两个点之间至多有唯一条简单路径，且对于这道题来讲非简单路径是没有意义的，因为非简单路径一定会囊括一个简单路径。这意味着对于每一个终点，至多有一个与之对应的距离最短的起点，使得当你将这条路径上某一条边删掉时，这个起点就不可能被到达了。那么我们显然会贪心的删去路径上编号最大的那一条。由于每一个点的入边(如果有的话)是唯一的，且没有修改操作，我们就可以用倍增来求路径最大值。

现在问题就转化为如何找每个重点对应的起点，我们分开考虑。

先考虑起点仅通过树边到达终点的情况。这个比较好办，将所有起点按照深度从小到大依次处理，每次把当前起点的深度当做标记覆盖到以这一起点所代表的的子树中，这个用线段树处理即可。做完这件事以后，扫一遍终点，如果它已经被覆盖到了，那么就通过标记和深度直接算出起点和终点的距离，倍增求一下最大值，最终答案取$\min$，然后把这个终点删掉即可。

剩下的终点一定满足没有一个起点能够仅通过树边到达，所以必须通过一部分环上的边，因而不在环上的起点也没用了，删掉即可。我们直接让剩下的终点先跳到它们所在的树的树根上，并在路径上的边求编号的$\max$，如果树根不在环上或树根所在的环上没有任何起点，那么这个中点本身就不可被任何起点到达，对答案没有贡献。然后对于每一个环，将起点和终点都按照顺时针排序，枚举每一个终点都一定能找到它的前驱起点，更新答案即可。

复杂度$O(N+\sum\limits_{i=1}^{m} (t_i+f_i)\log N)$

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define LL long long

#define M 200020

#define mid ((l+r)>>1)

using namespace std;

const int BufferSize=1<<19;

char buffer[BufferSize],*head,*tail;

inline char Getchar() {

    if(head==tail) {

        int l=fread(buffer,1,BufferSize,stdin);

        tail=(head=buffer)+l;

    } return *head++;

}

int read(){

	int nm=0,fh=1; char cw=Getchar();

	for(;!isdigit(cw);cw=Getchar()) if(cw=='-') fh=-fh;

	for(;isdigit(cw);cw=Getchar()) nm=nm*10+(cw-'0');

	return nm*fh;

}

int n,m,fs[M],fa[M][19],t[M][19],tmp=1,dfn[M],sz[M],od[M],to[M],nt[M];

int cnt,id[M],dep[M],tg[M<<2],maxn,tp[M],CT[M];

int S1[M],S2[M],C1[M],C2[M];

bool cir[M],vis[M],ist[M];

void link(int x,int y){nt[tmp]=fs[x],fs[x]=tmp,to[tmp++]=y;}

void dfs(int x){

	sz[x]=1,dfn[x]=++cnt,vis[x]=true;

	for(int i=fs[x];i!=-1;i=nt[i]){

		if(cir[to[i]]) continue; id[to[i]]=id[x];

		dep[to[i]]=dep[x]+1,tp[to[i]]=tp[x];

		dfs(to[i]),sz[x]+=sz[to[i]];

	}

}

bool cmpd(int x,int y){return dep[x]<dep[y];}

bool cmpc(int x,int y){if(id[tp[x]]!=id[tp[y]]) return id[tp[x]]<id[tp[y]];return od[tp[x]]>od[tp[y]];}

void pushdown(int x){if(tg[x]!=-1) tg[x<<1]=tg[x<<1|1]=tg[x],tg[x]=-1;}

void upd(int x,int l,int r,int L,int R,int D){

	if(r<L||R<l) return;

	if(L<=l&&r<=R){tg[x]=D;return;}

	pushdown(x),upd(x<<1,l,mid,L,R,D),upd(x<<1|1,mid+1,r,L,R,D);

}

int qry(int x,int l,int r,int pos){

	if(l==r) return tg[x]; pushdown(x);

	if(pos<=mid) return qry(x<<1,l,mid,pos); return qry(x<<1|1,mid+1,r,pos);

}

int dp(int x,int dt){

	int res=0;

	for(int k=0;dt>0;k++,dt>>=1) if(dt&1) res=max(res,t[x][k]),x=fa[x][k];

	return !res?m+1:res;

}

int main(){

	n=read(),m=read(),memset(fs,-1,sizeof(fs));

	for(int i=1;i<=m;i++){int u=read(),v=read();fa[v][0]=u,t[v][0]=i,link(u,v);}

	for(int i=1;i<=n;i++){

		if(vis[i]) continue; int now;

		for(vis[now=i]=true;fa[now][0]&&!vis[fa[now][0]];now=fa[now][0]) vis[fa[now][0]]=true;

		if(!fa[now][0]){

		 	ist[now]=true,t[now][0]=0;

			id[now]=++maxn,tp[now]=now,dfs(now); continue;

		}

		for(maxn++;!cir[now];now=fa[now][0]){

		    cir[now]=true,id[now]=maxn,tp[now]=now;

		    od[fa[now][0]]=od[now]+1,CT[maxn]++;

		} dfs(now);

		for(now=fa[now][0];od[now]!=CT[maxn];now=fa[now][0]) dfs(now);

	}

	for(int k=1;k<19;k++){

	    for(int i=1;i<=n;i++){

			fa[i][k]=fa[fa[i][k-1]][k-1];

			t[i][k]=max(t[i][k-1],t[fa[i][k-1]][k-1]);

		}

	}

	for(int Qs=read();Qs;--Qs){

		upd(1,1,n,1,n,-2);

		int now,m1=read(),m2,st=1,ed=1,ans=m+1,n1=0,n2=0,ps=1;

		for(int i=1;i<=m1;i++) S1[i]=read(); m2=read();

		for(int i=1;i<=m2;i++) S2[i]=read(); sort(S1+1,S1+m1+1,cmpd);

		for(int i=1;i<=m1;i++) upd(1,1,n,dfn[S1[i]],dfn[S1[i]]+sz[S1[i]]-1,dep[S1[i]]);

		for(int i=1;i<=m2;i++){

			if(!dep[S2[i]]){if(cir[tp[S2[i]]]) C2[++n2]=S2[i];continue;}

			int num=qry(1,1,n,dfn[S2[i]]),cst;

			if(num>=0) cst=dp(S2[i],dep[S2[i]]-num),ans=min(ans,cst);

			else C2[++n2]=S2[i];

		}

		for(int i=1;i<=m1;i++) if(cir[S1[i]]) C1[++n1]=S1[i];

		sort(C1+1,C1+n1+1,cmpc),sort(C2+1,C2+n2+1,cmpc),C1[n1+1]=C2[n2+1]=0;

		for(int i=1;i<=n2;i++){

			while(ed<n1&&id[C1[st]]<id[tp[C2[i]]]) st=ed+1,ed=ps=st;

			if(id[C1[st]]<id[tp[C2[i]]]) break;

			if(id[C1[st]]>id[tp[C2[i]]]) continue;

			while(ed<n1&&id[C1[st]]==id[C1[ed+1]]) ed++;

			now=cir[C2[i]]?0:dp(C2[i],dep[C2[i]]),C2[i]=tp[C2[i]];

			while(ps<ed&&od[C1[ps+1]]>od[C2[i]]) ps++;

			if(od[C1[ps]]>od[C2[i]]) now=max(now,dp(C2[i],od[C1[ps]]-od[C2[i]]));

			else now=max(now,dp(C2[i],CT[id[C1[ps]]]+od[C1[ed]]-od[C2[i]]));

			if(now) ans=min(ans,now);

		}

		if(ans==m+1) puts("OK"); else printf("%d\n",ans);

	}

	return 0;

}

巴特西

Statement

最新文章

热门文章