[LCA] 最近公共祖先

最近公共祖先求法很多, 各有优略

LCA步骤及原理:

---

 例题:

http://acm.hdu.edu.cn/showproblem.php?pid=2586

---

代码:

LCA倍增法

DFS + 向前星版
预处理DEG 为log2(n) + 1
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
//typedef __int128 ill;
const int MAXN = 1e6 + 10;
const ld PI = acos(-1.0);
const ld E = exp(1.0);
using namespace std;

int head[MAXN], cnt = 1, DEG;
struct node
{
    int to, next;
}edge[MAXN];
void insert(int x, int y)
{
    edge[cnt].next = head[x];
    head[x] = cnt;
    edge[cnt++].to = y;
    edge[cnt].next = head[y];
    head[y] = cnt;
    edge[cnt++].to = x;
}
int deep[MAXN] = {0}, fa[MAXN][20] = {0};
void dfs(int now, int pre)
{
    deep[now] = deep[pre] + 1;
    fa[now][0] = pre;
    for(int i = 1; i <= DEG; ++i)
        fa[now][i] = fa[ fa[now][i - 1] ][i - 1];
    for(int p = head[now]; p; p = edge[p].next)
    {
        int x = edge[p].to;
        if(x != pre)
            dfs(x, now);
    }
}
int lca(int x, int y)
{
    if(deep[x] > deep[y])
        swap(x, y);
    for(int i = DEG; i >= 0; --i)
    {
        if(deep[fa[y][i]] >= deep[x])
            y = fa[y][i];
    }
    
    if(x == y)
        return x;
    
    for(int i = DEG; i >= 0; --i)
    {
        if(fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    }
    
    return fa[x][0];
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int N, M, S;
    
    cin >> N >> M >> S;
    
    DEG = log2(N) + 1;
    
    for(int i = 1, from, to; i < N; ++i)
    {
        cin >> from >> to;
        insert(from, to);
    }
    
    dfs(S, 0);
    
    while(M--)
    {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << '
';
    }
    
    return 0;
}

/*
3 1
2 4
5 1
1 4
*/

 很复杂的一个版本

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ld PI = acos(-1.0);
const ld E = exp(1.0);
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 10;
const int DEG = 20;
const ll MOD = 1e9 + 7;

vector < pair <int, int> > edge[MAXN];

int deep[MAXN] = {0}, fa[MAXN][DEG]; //deep节点深度 fa[i][j]结点i的第2^j个爹
ll sum[MAXN] = {0}; //本题用的前缀和

int n, m;

void reset(int n)
{
	for(int i = 1; i <= n; ++i)
	{
		edge[i].clear();
	}
	memset(deep, 0, sizeof(int) * (n + 10));
	memset(fa, 0, sizeof(int) * (n + 10));
	memset(sum, 0, sizeof(int) * (n + 10));
	memset(used, 0, sizeof(int) * (n + 10));
}


void bfs(int root)
{
	queue <int> Q;
	deep[root] = 0;
	fa[root][0] = root;
	Q.push(root);
	while(!Q.empty())
	{
		int now = Q.front();
		Q.pop();
		for(int i = 1; i < DEG; ++i) //倍增处理爹
			fa[now][i] = fa[fa[now][i - 1]][i - 1];

		for(int i = 0; i < edge[now].size(); ++i)
		{
			int to = edge[now][i].first, val = edge[now][i].second;
			if(to == fa[now][0]) continue; //处理过爹了跳过
			deep[to] = deep[now] + 1; //记录深度
			fa[to][0] = now; //记录爹
			sum[to] = sum[now] + val; //本题记录的前缀和
			Q.push(to);
		}
	}
}

int lca(int u, int v)
{
	if(deep[u] > deep[v]) //调整深度
		swap(u, v);
	int hu = deep[u], hv = deep[v];
	int tu = u, tv = v;
	for(int det = hv - hu, i = 0; det; det >>= 1, ++i)
	{
		if(det & 1)
			tv = fa[tv][i];
	}//跳至同一深度

	if(tu == tv) return tu; //相同返回

	for(int i = DEG - 1; i >= 0; --i) //继续跳至相同
	{
		if(fa[tu][i] == fa[tv][i])
			continue;
		tu = fa[tu][i];
		tv = fa[tv][i];
	}
	return fa[tu][0];
} 

int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0);     cout.tie(0);
    //freopen("D://test.in", "r", stdin);
    //freopen("D://test.out", "w", stdout);
    
    int T;

    scanf("%d", &T);

    while(T--)
    {
    	scanf("%d%d", &n, &m);
		
		reset(n);
		
    	int x, y, z;

    	for(int i = 1; i < n; ++i)
    	{
    		scanf("%d%d%d", &x, &y, &z);
    		edge[x].push_back(make_pair(y, z));
    		edge[y].push_back(make_pair(x, z));
    	}

    	bfs(1);

    	while(m--)
    	{
    		int a, b;

    		scanf("%d%d", &a, &b);

    		int d = lca(a, b);
    		
    		ll ans = sum[a] + sum[b] - 2 * sum[d];

    		printf("%lld
", ans);
    	}
    }

    return 0;
}

O(n)暴力查找

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const ld PI = acos(-1.0);
const ld E = exp(1.0);
const int INF = 0x3f3f3f3f;
const int MAXN = 1e6 + 10;
const ll MOD = 1e9 + 7;

vector < pair <int, int> > edge[MAXN];

int deep[MAXN] = {0}, fa[MAXN];
bool used[MAXN] = {0};
ll sum[MAXN] = {0};

int n, m;

void reset(int n)
{
	for(int i = 1; i <= n; ++i)
	{
		edge[i].clear();
	}
	memset(deep, 0, sizeof(int) * (n + 10));
	memset(fa, 0, sizeof(int) * (n + 10));
	memset(sum, 0, sizeof(int) * (n + 10));
	memset(used, 0, sizeof(int) * (n + 10));
}

void dfs(int now)
{
	if(used[now])
		return ;

	used[now] = true;

	for(int i = 0; i < edge[now].size(); ++i)
	{
		int to = edge[now][i].first, val = edge[now][i].second;

		if(!used[to])
		{
			fa[to] = now;
			deep[to] = deep[now] + 1;
			sum[to] = sum[now] + val;
			dfs(to);
		}
	}
}

int lca(int c, int d)
{
	while(deep[c] > deep[d])
			c = fa[c];

	while(deep[d] > deep[c])
		d = fa[d];

	while(d != c)
		d = fa[d], c = fa[c];
		
	return d;
} 

int main()
{
    //ios::sync_with_stdio(false);
    //cin.tie(0);     cout.tie(0);
    //freopen("D://test.in", "r", stdin);
    //freopen("D://test.out", "w", stdout);
    
    int T;

    scanf("%d", &T);

    while(T--)
    {
    	scanf("%d%d", &n, &m);
		
		reset(n);
		
    	int x, y, z;

    	for(int i = 1; i < n; ++i)
    	{
    		scanf("%d%d%d", &x, &y, &z);
    		edge[x].push_back(make_pair(y, z));
    		edge[y].push_back(make_pair(x, z));
    	}

    	deep[1] = 1;

    	dfs(1);

    	while(m--)
    	{
    		int a, b;

    		scanf("%d%d", &a, &b);
    		
    		//cin >> a >> b;

    		int d = lca(a, b);
    		
    		ll ans = sum[a] + sum[b] - 2 * sum[d];

    		printf("%d
", ans);
    	}
    }

    return 0;
}