DataStructure/test/lca.test.cpp

View this file on GitHub
Last update: 2022-12-14 02:22:04+08:00
Problem: https://judge.yosupo.jp/problem/lca

Depends on

Code

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

#include <bits/stdc++.h>
using namespace std;

#include "../LCA.h"
#include "../../buffered_reader.h"

#define FOR(i, a, b) for (int i = (a), _##i = (b); i <= _##i; ++i)

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n = IO::get<int>();
    int q = IO::get<int>();
    vector<vector<int>> adj(n);
    FOR(i,1,n-1) {
        int pi = IO::get<int>();
        adj[i].push_back(pi);
        adj[pi].push_back(i);
    }

    LCA lca(n, adj, 0);

    while (q--) {
        int u = IO::get<int>();
        int v = IO::get<int>();

        cout << lca.lca(u, v) << '\n';
    }
    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

#line 1 "DataStructure/LCA.h"
// LCA
// Notes:
// - Index from 0
// - Cannot use for queries like min edge in path u -> v
//
// Tested:
// - https://judge.yosupo.jp/problem/lca
#line 1 "DataStructure/RMQ.h"
// RMQ {{{
//
// Sparse table
// Usage:
// RMQ<int, _min> st(v);
//
// Note:
// - doesn't work for empty range
//
// Tested:
// - https://judge.yosupo.jp/problem/staticrmq
template<class T, T (*op) (T, T)> struct RMQ {
    RMQ() = default;
    RMQ(const vector<T>& v) : t{v}, n{(int) v.size()} {
        for (int k = 1; (1<<k) <= n; ++k) {
            t.emplace_back(n - (1<<k) + 1);
            for (int i = 0; i + (1<<k) <= n; ++i) {
                t[k][i] = op(t[k-1][i], t[k-1][i + (1<<(k-1))]);
            }
        }
    }

    // get range [l, r-1]
    // doesn't work for empty range
    T get(int l, int r) const {
        assert(0 <= l && l < r && r <= n);
        int k = __lg(r - l);
        return op(t[k][l], t[k][r - (1<<k)]);
    }

private:
    vector<vector<T>> t;
    int n;
};
template<class T> T _min(T a, T b) { return b < a ? b : a; }
template<class T> T _max(T a, T b) { return a < b ? b : a; }
// }}}
#line 9 "DataStructure/LCA.h"
struct LCA {
    const int n;
    vector<vector<int>> adj;
    const int root;
    using P = pair<int,int>;
    static P f(P x, P y) { return std::min(x, y); }

    LCA(int _n, const vector<vector<int>>& _adj, int _root)
            : n(_n), adj(_adj), root(_root) {
        assert(0 <= root && root < n);
        id.resize(n);
        depth.resize(n);
        order.reserve(2 * n);
        dfs(root, -1, 0);
        rmq = RMQ<P, f>(order);
    }

    int lca(int u, int v) {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);

        int x = id[u], y = id[v];
        if (x > y) std::swap(x, y);
        return rmq.get(x, y+1).second;
    }

// private:
    vector<int> id, depth;
    vector<P> order;
    RMQ<P, f> rmq;

    void dfs(int u, int fu, int d) {
        id[u] = order.size();
        depth[u] = d;
        order.emplace_back(d, u);
        for (int v : adj[u]) {
            if (v == fu) continue;
            dfs(v, u, d + 1);
            order.emplace_back(d, u);
        }
    }
};
#line 1 "buffered_reader.h"
// Buffered reader {{{
namespace IO {
    const int BUFSIZE = 1<<14;
    char buf[BUFSIZE + 1], *inp = buf;

    bool reacheof;
    char get_char() {
        if (!*inp && !reacheof) {
            memset(buf, 0, sizeof buf);
            int tmp = fread(buf, 1, BUFSIZE, stdin);
            if (tmp != BUFSIZE) reacheof = true;
            inp = buf;
        }
        return *inp++;
    }
    template<typename T>
    T get() {
        int neg = 0;
        T res = 0;
        char c = get_char();
        while (!std::isdigit(c) && c != '-' && c != '+') c = get_char();
        if (c == '+') { neg = 0; }
        else if (c == '-') { neg = 1; }
        else res = c - '0';

        c = get_char();
        while (std::isdigit(c)) {
            res = res * 10 + (c - '0');
            c = get_char();
        }
        return neg ? -res : res;
    }
};
// Helper methods
int ri() {
    return IO::get<int>();
}
// }}}
#line 8 "DataStructure/test/lca.test.cpp"

#define FOR(i, a, b) for (int i = (a), _##i = (b); i <= _##i; ++i)

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n = IO::get<int>();
    int q = IO::get<int>();
    vector<vector<int>> adj(n);
    FOR(i,1,n-1) {
        int pi = IO::get<int>();
        adj[i].push_back(pi);
        adj[pi].push_back(i);
    }

    LCA lca(n, adj, 0);

    while (q--) {
        int u = IO::get<int>();
        int v = IO::get<int>();

        cout << lca.lca(u, v) << '\n';
    }
    return 0;
}