LCA算法板子

LCA

tarjan

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 5e5 + 7;
vector<ll> G[N], Q[N];
ll ans[N][3], fa[N], n, m, s;
ll vis[N];

void init()
{
    for (ll i = 0; i < N; i++)
        fa[i] = i;
}

int find(int x)
{
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

void tarjan(int u) {
    vis[u] = 1;//标记该点已被访问
    for (auto i : Q[u]) {
        if (vis[ans[i][1]] && vis[ans[i][0]])
            ans[i][2] = find(ans[i][0] == u ? ans[i][1] : ans[i][0]);
    }
    for (auto v : G[u]) {//父亲是靠近根节点的节点
        if (vis[v])
            continue;
        tarjan(v);
        fa[v] = u;//v的子节点已全部访问完
    }
}

signed main() {
    init();
    cin >> n >> m >> s;//顶点数、询问次数、根节点
    for (int i = 1, x, y; i < n; i++)
        cin >> x >> y, G[x].push_back(y), G[y].push_back(x);//存图
    for (int i = 1; i <= m; i++)//存询问
    {
        cin >> ans[i][0] >> ans[i][1];
        Q[ans[i][0]].push_back(i);
        Q[ans[i][1]].push_back(i);
    }
    tarjan(s);
    for (int i = 1; i <= m; i++)
        cout << ans[i][2] << '\n';
    return 0;
}

倍增

两个节点到达同一节点后，不论怎么向上走，达到的显然还是同一节点

int fa[21][N], dep[N];
void dfs(int x, int pre, int d)//找到每个节点父亲与深度
{
	fa[0][x] = pre;
	dep[x] = d;
	for(auto &to : g[x]) if(to != pre) dfs(to, x, d + 1);
}
int LCA(int u, int v)
{
	if(dep[u] > dep[v]) swap(u, v);
	int temp = dep[v] - dep[u];//将u v移到同一深度
	for(int i = 0; ((1 << i) <= temp); i++) if((1 << i) & temp) v = fa[i][v];
	if(u == v) return u;
	for(int i = log2(n); i >= 0; i--)//两个节点一起往上走
	{								 //最多合法的跳跃是 2 ^ log2(n)
		if(fa[i][u] != fa[i][v])//如果相同则代表跳的太多了
		{
			u = fa[i][u];
			v = fa[i][v];
		}
	}
	return fa[0][u];
}
void init_LCA()// 注意根节点是什么，dfs 默认是根节点是 1 
{
    for(int j = 0; j <= 20; j++) for( int i = 1; i <= n; i++) fa[j][i] = 0;
	dfs(root, -1, 0);
	for(int j = 0; (1 << j) <= n; j++)//预处理出每个节点往上走2^j所到的节点，超过根节点记为-1
	{
		for(int i = 1; i <= n; i++) 
		{
			if(fa[j][i] < 0) fa[j + 1][i] = -1;
			else fa[j + 1][i] = fa[j][fa[j][i]];
		}
	}
}