MLE on #2 、#3

思路：缩点+树剖

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,x,y;
struct edge{int x,y;}e[N];
int dfn[N],tot,low[N],co[N],col;
bool bridge[N];
vector<pair<int,int> >p[N],g[N];

void tarjan(int u,int from){
	dfn[u]=low[u]=++tot;
	for(int i=0;i<g[u].size();i++){
		int v=g[u][i].first;
		if(v==from)continue;
		if(!dfn[v]){
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])bridge[g[u][i].second]=true;
		}
		else low[u]=min(low[u],dfn[v]);
	}
}

void getco(int x,int col){
	co[x]=col;
	for(int i=0;i<g[x].size();i++){
		int y=g[x][i].first,z=g[x][i].second;
		if(!bridge[z]&&!co[y])getco(y,col);
	}
}
int dep[N],fa[N],num[N],son[N],in[N],out[N],top[N],tot_time,nw[N];
void dfs1(int x,int from){
	dep[x]=dep[from]+1;
	fa[x]=from;
	for(int i=0;i<p[x].size();i++){
		int y=p[x][i].first;
		if(y!=from){
			dfs1(y,x);
			num[x]+=num[y];
			if(num[y]>num[son[x]])son[x]=y;
		}
	}num[x]++;
}
void dfs2(int x,int tp,int from){
	top[x]=tp;
	in[x]=++tot_time;
	if(!son[x]){out[x]=tot_time;return ;}
	dfs2(son[x],tp,x);
	for(int i=0;i<p[x].size();i++){
		int y=p[x][i].first,z=p[x][i].second;
		if(y!=from&&y!=son[x]){
			dfs2(y,y,x);
		}nw[z]=in[y];
	}out[x]=tot_time;
}
int w[N*4];
int ask(int l,int r,int x,int m){
	if(w[m]||l==r)return w[m];
	else {
		int mid=(l+r)>>1;
		if(x<=mid)return ask(l,mid,x,m*2);
		else return ask(mid+1,r,x,m*2+1);
	}
}
void change(int l,int r,int x,int y,int m,int k){
	if(x<=l&&r<=y)w[m]=k;
	else {
		int mid=(l+r)>>1;
		if(x<=mid)change(l,mid,x,y,m*2,k);
		if(y>mid)change(mid+1,r,x,y,m*2+1,k);
	}
}
void replace(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]){
			change(1,col,in[top[x]],in[x],1,2);
			x=fa[top[x]];
		}else {
			change(1,col,in[top[y]],in[y],1,1);
			y=fa[top[y]];
		}
	}
	if(x==y)return ;
	if(dep[x]>dep[y])change(1,col,in[son[y]],in[x],1,2);
	else change(1,col,in[son[x]],in[y],1,1);
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&e[i].x,&e[i].y);
		g[e[i].x].push_back(make_pair(e[i].y,i));
		g[e[i].y].push_back(make_pair(e[i].x,i));
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,i);
	for(int i=1;i<=n;i++)if(!co[i])getco(i,++col);
	for(int i=1;i<=m;i++){
		x=co[e[i].x],y=co[e[i].y];
		if(x!=y){
			p[x].push_back(make_pair(y,i));
			p[y].push_back(make_pair(x,i));
		}
	}
	dfs1(1,1);
	dfs2(1,1,1);
	int q;
	scanf("%d",&q);
	while(q--){
		scanf("%d%d",&x,&y);
		if(co[x]!=co[y])replace(co[x],co[y]);
	}
	for(int i=1;i<=m;i++){
		x=e[i].x,y=e[i].y;
		if(co[x]==co[y])printf("B");
		else {
			int NOW=ask(1,col,nw[i],1);
			if(!NOW)printf("B");
			else if((NOW==1&&dep[co[x]]<dep[co[y]])||(NOW==2&&dep[co[x]]>dep[co[y]]))printf("R");
			else printf("L");
		}
	}
	return 0;
}