MLE on #7 #9 #10 #11

#include <iostream>
#include <stack>
#include <vector>
#include <cstdlib>
#include <set>
using namespace std;
int n,m;
const int Maxn=100005,Maxm=500005;
int nxt[Maxm*2],to[Maxm*2],head[Maxn],edge=1;
vector<int> adj[Maxn];
set<pair<int,int> > chong;
void add(int u,int v)
{
	to[++edge]=v;
	nxt[edge]=head[u];
	head[u]=edge;
}
int dft,pre[Maxn],low[Maxn],dcc[Maxn],dccCount,bridge[Maxm*2];
stack<int> st;
void tarjan(int u,int fa)
{
	pre[u]=low[u]=++dft;
	for(int now=head[u];now;now=nxt[now])
	{
		int v=to[now];
		if(v==fa) continue;
		if(!pre[v])
		{
			tarjan(v,u);
			low[u]=min(low[v],low[u]);
//			cout<<u<<" "<<v<<" "<<low[v]<<" "<<pre[u]<<endl;
			if(low[v]>pre[u])
				bridge[now]=bridge[now^1]=1;
		}
		else low[u]=min(low[u],pre[v]);
	}
}
void dfsdcc(int u)
{
	dcc[u]=dccCount;
	for(int now=head[u];now;now=nxt[now])
	{
		int v=to[now];
		if(dcc[v]||bridge[now]) continue;
		dfsdcc(v);
	}
}
int lg[Maxn],anc[Maxn][20],dep[Maxn];
void init(){for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(i==(1<<lg[i-1]));}
void dfs(int u,int father)
{
	dep[u]=dep[father]+1;
	anc[u][0]=father;
	for(int i=1;(1<<i)<=dep[u];i++)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for(int now=head[u];now;now=nxt[now])
	{
		int v=to[now];
		if(v!=father) dfs(v,u);
	}
}
int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	while(dep[x]>dep[y])
		x=anc[x][lg[dep[x]-dep[y]]-1];
	if(x==y) return x;
	for(int i=lg[dep[x]]-1;i>=0;i--)
	{
		if(anc[x][i]!=anc[y][i])
		{
			x=anc[x][i];
			y=anc[y][i];
		}
	}
	return anc[x][0];
}
void out(int x)
{
	while(x)
	{
		st.push(x&1);
		x>>=1;
	}
	while(!st.empty())
	{
		printf("%d",st.top());
		st.pop();
	}
}
int main()
{
	int u,v,q;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		if(u>v) swap(u,v);
		if(chong.count(make_pair(u,v))) continue;
		chong.insert(make_pair(u,v));//set去重边
		add(u,v);
		add(v,u);
	}
	for(int i=1;i<=n;i++)
		if(!pre[i]) tarjan(i,0);
	for(int i=1;i<=n;i++)
	{
		if(!dcc[i])
		{
			dccCount++;
			dfsdcc(i);
		}
	}
	for(int u=1;u<=n;u++)
	{
		for(int now=head[u];now;now=nxt[now])
		{
			if(!bridge[now]) continue;
			int v=to[now];
			if(u>v) continue;
//			if(dcc[u]==dcc[v]) continue;
			adj[dcc[v]].push_back(u);
			adj[dcc[u]].push_back(v);
		}
	}
	init();
	dfs(1,0);
	cin>>q;
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d",&u,&v);
		u=dcc[u];v=dcc[v];
		out(dep[u]+dep[v]-dep[lca(u,v)]*2+1);
		printf("\n");
	}
	return 0;
}

如果把lca段换成这个

void init()
{
	for(int i=1;i<=13;i++) lg[1<<i]=1;
	for(int i=1;i<=10000;i++) lg[i]+=lg[i-1];
}
void dfs(int u,int fa)
{
	dep[u]=dep[fa]+1;
	anc[u][0]=fa;
	for(int i=1;(1<<i)<dep[u];i++)
		anc[u][i]=anc[anc[u][i-1]][i-1];
	for(int i=0;i<adj[u].size();i++)
	{
		int v=adj[u][i];
		if(v==fa) continue;
		dfs(v,u);
	}
}
int lca(int u,int v)
{
	if(dep[u]<dep[v]) swap(u,v);
	while(dep[u]>dep[v]) u=anc[u][lg[dep[u]-dep[v]]];
	if(u==v) return u;
	for(int i=lg[dep[u]];i;i--)
	{
		if(anc[u][i]!=anc[v][i])
		{
			u=anc[u][i];
			v=anc[v][i];
		}
	}
	return anc[u][0];
}

则WA on #8 #9 #10 #11
路过的好心人看一眼叭 球球了