Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // LCA using Segment Tree
- // by Lawrence Melo
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 50100;
- vector<int> G[maxn];
- int cam[4*maxn], tree[4*maxn], d[maxn], num, f[maxn];
- bool vis[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(0);
- 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);
- }
Add Comment
Please, Sign In to add comment