lca.cpp

// LCA using Segment Tree
// by Lawrence Melo

#include <bits/stdc++.h>
using namespace std;
const int maxn =  50100;

vector<int> G[maxn];
int cam[2*maxn], tree[4*maxn], d[maxn], num, f[maxn];

void euler(int x, int y) // euler tour
{
	f[x] = ++num;
	cam[num] = x;
	d[x] = d[y] + 1;
	for(auto u : G[x])
	{
		if(u == y) continue;
		euler(u, x);
		cam[++num] = x;
	}
}

int op(int a, int b)
{
	if(d[a] < d[b]) return a;
	else return b;
}

void build(int no, int l , int r)
{
	if(l == r)
		tree[no] = cam[l];
	else
	{
		int m = (l + r) / 2;
		build(2*no, l , m);
		build(2*no + 1, m + 1, r);
		tree[no] = op(tree[2*no], tree[2*no + 1]);
	}
}

int query(int no, int l, int r, int a , int b)
{
	if(a <= l and r <= b)
		return tree[no];
	int m = (l + r) / 2;

	if(b <= m) return query(2*no, l , m, a , b);
	if(a > m) return query(2*no + 1, m + 1, r, a, b);

	return op(query(2*no, l , m, a , b), query(2*no + 1, m + 1, r, a , b));
}

int LCA(int a , int b)
{
	if(f[a] > f[b]) swap(a, b);
	return query(1, 1, num, f[a], f[b]);
}


int n;

int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);
	cin >> n;
	
	for(int i = 0; i < n - 1; i++)
	{
		int a , b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	euler(1, 1);

	build(1, 1, num);

}