test/lowest_common_ancestor.aoj.GRL_5_C.test.cpp

View this file on GitHub
Last update: 2020-05-09 18:52:06+09:00
Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_C

Depends on

lib/lowest_common_ancestor.hpp

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_C"

#include <iostream>
#include <vector>
#include "../lib/lowest_common_ancestor.hpp"

int main() {
    int n; std::cin>> n;
    std::vector<std::vector<int>> edg(n);
    bool used[100003] = {};
    for (int i = 0; i < n; i++) {
        int k; std::cin >> k;
        for (int j = 0; j < k ;j++) {
            int c; std::cin >> c;
            edg[i].push_back(c);
            edg[c].push_back(i);
            used[c] = true;
        }
    }
    int root;
    for (int i = 0; i < n; i++) {
        if (!used[i]) root = i;
    }
    LowestCommonAncestor lca(edg, root);
    int q; std::cin >> q;
    while (q--) {
        int u, v; std::cin >> u >> v;
        std::cout << lca.query(u, v) << std::endl;
    }
    return 0;
}

#line 1 "test/lowest_common_ancestor.aoj.GRL_5_C.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/5/GRL_5_C"

#include <iostream>
#include <vector>
#line 1 "lib/lowest_common_ancestor.hpp"



#line 5 "lib/lowest_common_ancestor.hpp"
#include <utility>

struct LowestCommonAncestor {
    using Edge = std::vector<std::vector<int>>;
    std::vector<int> depth;
    std::vector<std::vector<int>> anc;

    LowestCommonAncestor(const Edge &edg, int root)
        : depth(edg.size()), anc(L, std::vector<int>(edg.size(), root)) {

        build(edg, root);
    }

    int query(int u, int v) {
        if (depth[u] > depth[v]) std::swap(u, v);
        for (int i = L - 1; i >= 0; i--) {
            if (((depth[v] - depth[u]) >> i) & 1) {
                v = anc[i][v];
            }
        }
        if (u == v) return u;

        for (int i = L - 1; i >= 0; i--) {
            if (anc[i][u] == anc[i][v]) continue;
            u = anc[i][u];
            v = anc[i][v];
        }
        return anc[0][u];
    }

private:
    static const int L = 30;

    void dfs(const Edge &edg, int pos, int prev = -1) {
        for (int v : edg[pos]) {
            if (v == prev) continue;
            depth[v] = depth[pos] + 1;
            anc[0][v] = pos;
            dfs(edg, v, pos);
        }
    }

    void build(const Edge &edg, int root) {
        dfs(edg, root);
        int n = edg.size();
        for (int i = 1; i < L; i++) {
            for (int j = 0; j < n; j++) {
                anc[i][j] = anc[i - 1][anc[i - 1][j]];
            }
        }
    }
};


#line 6 "test/lowest_common_ancestor.aoj.GRL_5_C.test.cpp"

int main() {
    int n; std::cin>> n;
    std::vector<std::vector<int>> edg(n);
    bool used[100003] = {};
    for (int i = 0; i < n; i++) {
        int k; std::cin >> k;
        for (int j = 0; j < k ;j++) {
            int c; std::cin >> c;
            edg[i].push_back(c);
            edg[c].push_back(i);
            used[c] = true;
        }
    }
    int root;
    for (int i = 0; i < n; i++) {
        if (!used[i]) root = i;
    }
    LowestCommonAncestor lca(edg, root);
    int q; std::cin >> q;
    while (q--) {
        int u, v; std::cin >> u >> v;
        std::cout << lca.query(u, v) << std::endl;
    }
    return 0;
}