tarjan LCA求条

j27eGU 2025-05-18 11:40:54

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=500005;
int fa[MAXN],vis[MAXN],ans[MAXN];
vector<int> g[MAXN];
vector<int> query[MAXN],query_id[MAXN];
int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
void tarjan(int x)
{
	vis[x]=1;
	for(int i=0;i<g[x].size();i++)
	{
		int y=g[x][i];
		if(vis[y])continue;
		tarjan(y);
		fa[y]=x;
	}
	for(int i=0;i<query[x].size();i++)
	{
		int y=query[x][i],id=query_id[x][i];
		if(vis[y]==2)
		{
			ans[id]=find(y);
		}
	}
	vis[x]=2;
}
int main()
{
	int n,m,s;
	cin>>n>>m>>s;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		query[x].push_back(y);
		query[y].push_back(x);
		query_id[x].push_back(i);
		query_id[y].push_back(i);
	}
	tarjan(s);
	for(int i=1;i<=m;i++)cout<<ans[i]<<endl;
}

j27eGU

2025-05-20 19:06:23

@wpx001，您的代码就是倍增的，我已经会了，但是两种都会应该是比较稳妥的办法

j27eGU

2025-05-20 19:02:51

就算会拿我的代码去洛谷提交也是不能全对的啊

j27eGU

2025-05-20 19:02:15

不是，你没代码怎么调

2025-05-20 8:05:07

让调，你tm发代码是几个意思啊

j27eGU

2025-05-18 23:19:05

少了一行代码……

j27eGU

2025-05-18 23:18:50

已经条完了

wpx001

2025-05-18 19:17:46

不常用，可以试试这个

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
int n,q,r,x,y,tot,head[N],dep[N],f[N][21];
struct node{
	int to,nxt;
}edge[N * 2];
void add(int x,int y)
{
	edge[++tot].to = y;
	edge[tot].nxt = head[x];
	head[x] = tot;
}
void dfs(int x,int fa)
{
	dep[x] = dep[fa] + 1;
	for(int i = head[x];i != -1;i = edge[i].nxt)
	{
		int y = edge[i].to;
		if(y != fa)
		{
			f[y][0] = x;
			dfs(y,x);
		}
	}
}
void pre()
{
	for(int j = 1;(1 << j) <= n;j++) for(int i = 1;i <= n;i++) if(f[i][j - 1] != -1) f[i][j] = f[f[i][j - 1]][j - 1];
}
int lca(int x,int y)
{
	if(dep[y] < dep[x]) swap(x,y);
	int k = log2(dep[y]) + 1;
	for(int i = k;i >= 0;i--) if(dep[y] - (1 << i) >= dep[x]) y = f[y][i];
	if(x == y) return x;
	for(int i = k;i >= 0;i--) if(f[x][i] != -1 && f[x][i] != f[y][i]) x = f[x][i],y = f[y][i];
	return f[x][0];
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	memset(f,-1,sizeof f);
	memset(head,-1,sizeof head);
	cin >> n >> q >> r;
	for(int i = 1;i < n;i++)
	{
		cin >> x >> y;
		add(x,y);
		add(y,x);
	}
	dfs(r,0);
	pre();
	for(int i = 1;i <= q;i++)
	{
		cin >> x >> y;
		cout << lca(x,y) << '\n';
	}
	return 0;
}

tarjan LCA求条

共 7 条回复