Tree/Lowest_common_ancestor.test.cpp

• View this file on GitHub
• Last update: 2025-06-11 15:37:14+07:00
• Problem: https://judge.yosupo.jp/problem/lca

Depends on

• Tree/Tree/Lca.h
• template.h

Code

#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#include "../template.h"
#include "Tree/Lca.h"

void solve() {
    int n, q; cin >> n >> q;
    Lca lca(n);
    for (int i = 1; i <= n-1; i++) {
        int x; cin >> x;
        lca.tree[i].emplace_back(x);
        lca.tree[x].emplace_back(i);
    }
    lca.dfs(0, -1);
    while (q--) {
        int u, v; cin >> u >> v;
        cout << lca.query(u, v) << '\n';
    }
}

#line 1 "Tree/Lowest_common_ancestor.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"

#line 2 "template.h"

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define MOD (ll)(1e9+7)
#define all(x) (x).begin(),(x).end()
#define unique(x) x.erase(unique(all(x)), x.end())
#define INF32 ((1ull<<31)-1)
#define INF64 ((1ull<<63)-1)
#define inf (ll)1e18

#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

const int mod = 998244353;

void solve();

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    // cin.exceptions(cin.failbit);
    // int t; cin >> t;
    // while(t--)
        solve();
    cerr << "\nTime run: " << 1000 * clock() / CLOCKS_PER_SEC << "ms" << '\n';
    return 0;
}
#line 2 "Tree/Tree/Lca.h"

struct Lca {
    vector<vector<int>> tree, up;
    vector<int> h;

    Lca() {}
    Lca(int n): tree(n+1), up(n+1, vector<int>(20)), h(n+1, 0) {}

    void dfs(int u, int p) {
        for(int v : tree[u]) {
            if(v == p) continue;
            up[v][0] = u;
            h[v] = h[u] + 1;
            for(int j = 1; j < 20; j++) {
                up[v][j] = up[up[v][j-1]][j-1];
            }
            dfs(v, u);
        }
    }

    void addEdge(int u, int v) {
        tree[u].emplace_back(v);
        tree[v].emplace_back(u);
    }

    int query(int u, int v) {
        if(h[u] < h[v]) swap(u, v);
        int k = h[u]-h[v];
        u = ancestor_k(u, k);
        if(u == v) return u;

        k = __lg(h[u]);
        for(int j = k; j >= 0; j--) {
            if(up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
        return up[u][0];
    }

    int dist(int u, int v) {
        int node = query(u, v);
        return h[u] + h[v] - 2 * h[node];
    }

    int ancestor_k(int u, int k) {
        for(int j = 0; (1 << j) <= k; j++) {
            if(k >> j & 1)
                u = up[u][j];
        }
        return u;
    }
};
#line 5 "Tree/Lowest_common_ancestor.test.cpp"

void solve() {
    int n, q; cin >> n >> q;
    Lca lca(n);
    for (int i = 1; i <= n-1; i++) {
        int x; cin >> x;
        lca.tree[i].emplace_back(x);
        lca.tree[x].emplace_back(i);
    }
    lca.dfs(0, -1);
    while (q--) {
        int u, v; cin >> u >> v;
        cout << lca.query(u, v) << '\n';
    }
}

Back to top page