Language: C++


#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
using ll = long long;
using ld = long double;
constexpr ll MOD = 1000000007LL;
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;
template <typename Functor>
struct fix_type
{
    Functor functor;
    template <typename... Args>
    decltype(auto) operator()(Args&&... args) const& { return functor(functor, std::forward<Args>(args)...); }
};
template <typename Functor>
fix_type<typename std::decay<Functor>::type> fix(Functor&& functor) { return {std::forward<Functor>(functor)}; }



struct Graph
{
    Graph(const int v) : V{v}, edge(v), rev_edge(v) {}
    void addEdge(const int from, const int to)
    {
        edge[from].push_back(to);
        rev_edge[to].push_back(from);
    }
    const int V;
    vector<vector<int>> edge;
    vector<vector<int>> rev_edge;
};



class LowestCommonAncestor
{
public:
    LowestCommonAncestor(const Graph& g, const int root = 0) : left(g.V, 0)  // 無向根付き木
    {
        vector<bool> used(g.V, false);
        auto dfs = fix([&](auto&& self, const pair<int, int>& s) -> void {
            used[s.second] = true;
            const int pos = s.second;
            left[pos] = depth.size();
            depth.push_back(s);
            for (const int to : g.edge[pos]) {
                if (used[to]) { continue; }
                self(self, {s.first + 1, to});
                depth.push_back(s);
            }
        });
        dfs(make_pair(0, root));
    }
    int LCA(const int u, const int v) const
    {
        static const SparseTable<DepthMin> st{depth};
        const int ul = left[u];
        const int vl = left[v];
        return st.accumulate(min(ul, vl), max(ul, vl) + 1).second;
    }

private:
    struct DepthMin
    {
        using T = pair<int, int>;
        T operator()(const T& a, const T& b) const { return min(a, b); }
    };
    vector<int> left;
    vector<pair<int, int>> depth;
};



template <typename Base>
class SparseTable
{
public:
    using T = typename Base::T;
    using SemiLattice = Base;
    SparseTable(const vector<T>& val)
        : size(val.size()), lg2(size + 1, 0)
    {
        for (int i = 2; i <= size; i++) {
            lg2[i] = lg2[i / 2] + 1;
        }
        table.resize(size, vector<T>(lg2[size] + 1));
        for (int i = 0; i < size; i++) {
            table[i][0] = val[i];
        }
        for (int j = 0; j < lg2[size]; j++) {
            const int w = 1 << j;
            for (int i = 0; i <= size - (w << 1); i++) {
                T tl = table[i][j], tr = table[i + w][j];
                table[i][j + 1] = op(tl, tr);
            }
        }
    }
    T accumulate(const int l, const int r) const
    {
        assert(0 <= l and l < r and r <= size);
        const int j = lg2[r - l];
        return op(table[l][j], table[r - (1 << j)][j]);
    }

private:
    const int size;
    vector<int> lg2;
    vector<vector<T>> table;
    const SemiLattice op{};
};



// Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C
// Status: Accepted

int main()
{
    int n;
    cin >> n;
    Graph g(n);
    for (int i = 0; i < n; i++) {
        int k;
        cin >> k;
        for (int j = 0; j < k; j++) {
            int c;
            cin >> c;
            g.addEdge(i, c);
        }
    }

    LowestCommonAncestor lca{g};
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int u, v;
        cin >> u >> v;
        cout << lca.LCA(u, v) << endl;
    }
    return 0;
}



Compiler output:
a.cc: In member function 'int LowestCommonAncestor::LCA(int, int) const':
a.cc:58:22: error: 'SparseTable' does not name a type
   58 |         static const SparseTable<DepthMin> st{depth};
      |                      ^~~~~~~~~~~
a.cc:61:16: error: 'st' was not declared in this scope; did you mean 'std'?
   61 |         return st.accumulate(min(ul, vl), max(ul, vl) + 1).second;
      |                ^~
      |                std