关于

void Tarjan(int x){
	go[x]=1;	
	for(int i=h[x];i;i=net[i]){
		int y=v[i];
		if(!go[y]){
			depth[y]=depth[x]+1;
			Tarjan(y);
			merge(y,x);
		}
	}
	int l=vec[x].size();
	for(int i=0;i<l;i++){
		int y=vec[x][i].first;
		int id=vec[x][i].second;
		//if(go[y]==2){
			int z=Find(y);
			lca[id]=max(depth[x]+depth[y]-depth[z]*2+1,0);
	//	}
	}
//	go[x]=2;
}

和

void Tarjan(int x){
	go[x]=1;	
	for(int i=h[x];i;i=net[i]){
		int y=v[i];
		if(!go[y]){
			depth[y]=depth[x]+1;
			Tarjan(y);
			merge(y,x);
		}
	}
	int l=vec[x].size();
	for(int i=0;i<l;i++){
		int y=vec[x][i].first;
		int id=vec[x][i].second;
		if(go[y]==2){
			int z=Find(y);
			lca[id]=max(depth[x]+depth[y]-depth[z]*2+1,0);
		}
	}
	go[x]=2;
}

这两种有什么区别

为什么第一个能A第二个就不行？

可能是我的问题？XD

附源代码

#include<bits/stdc++.h>
#include<vector>
#define G =getchar()
#define R =read()

using namespace std;

typedef pair<int,int> P;
const int MAXN=5e4+10;
int n,m,q;
int dfn[MAXN],low[MAXN],tim;
int c[MAXN],group,fa[MAXN],sum;
int depth[MAXN];
int lca[MAXN];
bool a[10001][10001];
int go[MAXN];
int vis[MAXN],br[MAXN*2];
//int head[MAXN],ver[MAXN*2],nxt[MAXN*2];
int cnt=1;
vector<P>uto[MAXN];
int h[MAXN],v[MAXN*2],net[MAXN*2],tot=1;
vector<P>vec[MAXN];

int read(){
	int x=0,f=1;
	char ch G;
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch G;
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch G;
	}
	return x*f;
}

void logprint(int x){
	if(x>1)logprint(x>>1);
	int a=x&1;
	putchar(a+'0');
}

void add_(int x,int y){
	v[++tot]=y;
	net[tot]=h[x];
	h[x]=tot;
}

int Find(int x){
	if(fa[x]==x)return x;
	return fa[x]=Find(fa[x]);
}

void merge(int x,int y){
	fa[Find(x)]=fa[Find(y)];
}

void Tarjan(int x){
	go[x]=1;	
	for(int i=h[x];i;i=net[i]){
		int y=v[i];
		if(!go[y]){
			depth[y]=depth[x]+1;
			Tarjan(y);
			merge(y,x);
		}
	}
	int l=vec[x].size();
	for(int i=0;i<l;i++){
		int y=vec[x][i].first;
		int id=vec[x][i].second;
		//if(go[y]==2){
			int z=Find(y);
			lca[id]=max(depth[x]+depth[y]-depth[z]*2+1,0);
	//	}
	}
//	go[x]=2;
}

void tarjan(int x,int f){
	dfn[x]=low[x]=++tim;
	for(int i=0;i<uto[x].size();i++){
		int y=uto[x][i].first;
		int iv=uto[x][i].second;
		if(y==f)continue;
		if(!dfn[y]){
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
			if(low[y]>dfn[x])br[iv]=br[iv^1]=1;
		}
		else{
			low[x]=min(low[x],dfn[y]);
		}
	}
}

void dfs(int x){
	c[x]=group;
	for(int i=0;i<uto[x].size();i++){
		int y=uto[x][i].first;
		int iv=uto[x][i].second;
		if(c[y]||br[iv])continue;
		dfs(y);
	}
}

int main(){
	n R;m R;
	for(int i=1;i<=m;i++){
		int u R,v R;
		if(a[u][v]||a[v][u])continue;
		a[u][v]=a[v][u]=1;
		uto[u].push_back(P(v,++cnt));
		uto[v].push_back(P(u,++cnt));
	}
	
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i,0);
		}
	}
	for(int i=1;i<=n;i++){
		if(!c[i]){
			group++;
			dfs(i);
		}
	}
	for(int i=1;i<=n;i++){
		fa[i]=i;

	}
	for(int x=1;x<=n;x++){
		for(int i=0;i<uto[x].size();i++){
			int y=uto[x][i].first;
			if(c[x]==c[y])continue;
			add_(c[x],c[y]);
			add_(c[y],c[x]);
		}
	}

	q R;
	for(int i=1;i<=q;i++){
		int x R,y R;
		if(x==y){
			lca[i]=1;
			continue;
		}
		vec[c[x]].push_back(P(c[y],i));
		vec[c[y]].push_back(P(c[x],i));
		
	}
	for(int i=1;i<=group;i++){
		if(!go[i]){
			depth[i]=1;
			Tarjan(i);
		}
	}
	for(int i=1;i<=q;i++){
		logprint(lca[i]);
		putchar('\n');
	}
	return 0;
}

如上，这样跑LCA就能A

求大佬解答