test/tarjan_offline_lca.test.cpp

• View this file on GitHub
• Last update: 2022-09-04 17:18:59+00:00
• Problem: https://judge.yosupo.jp/problem/lca

Depends on

• lca/tarjan_offline_lca.hpp

Code

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

#include "../lca/tarjan_offline_lca.hpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<std::vector<int>> adj(N);
    for (auto i = 1; i < N; ++i) {
        int p;
        std::cin >> p;
        adj[p].push_back(i);
    }
    std::vector<std::pair<int, int>> queries(Q);
    for (auto &[u, v] : queries) {
        std::cin >> u >> v;
    }
    tarjan_offline_lca lca(adj, 0, queries);
    auto result = lca.lca();
    for (auto x : result) {
        std::cout << x << '\n';
    }
}

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

#line 1 "lca/tarjan_offline_lca.hpp"



#include <utility>
#include <vector>

struct dsu {
    dsu(int n) : parent_or_size(n, -1) {}
    int find(int u) {
        return parent_or_size[u] < 0
                   ? u
                   : parent_or_size[u] = find(parent_or_size[u]);
    }
    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u != v) {
            if (-parent_or_size[u] < -parent_or_size[v]) {
                std::swap(u, v);
            }
            parent_or_size[u] += parent_or_size[v];
            parent_or_size[v] = u;
        }
    }

private:
    std::vector<int> parent_or_size;
};

struct tarjan_offline_lca {
    tarjan_offline_lca(const std::vector<std::vector<int>> &graph, int root,
                       const std::vector<std::pair<int, int>> &queries)
        : graph_(graph), root_(root), queries_(graph.size()),
          result_(queries.size()), ancestor_(graph.size()), color_(graph.size()),
          d_(graph.size()) {
        auto q = static_cast<int>(queries.size());
        for (auto i = 0; i < q; ++i) {
            auto [u, v] = queries[i];
            queries_[u].push_back({v, i});
            queries_[v].push_back({u, i});
        }
    }
    std::vector<int> lca() {
        lca(root_, root_);
        return result_;
    }

private:
    void lca(int u, int parent) {
        ancestor_[d_.find(u)] = u;
        for (auto v : graph_[u])
            if (v != parent) {
                lca(v, u);
                d_.merge(u, v);
                ancestor_[d_.find(u)] = u;
            }
        color_[u] = 1;
        for (auto [v, i] : queries_[u]) {
            if (color_[v]) {
                result_[i] = ancestor_[d_.find(v)];
            }
        }
    }
    std::vector<std::vector<int>> graph_;
    int root_;
    std::vector<std::vector<std::pair<int, int>>> queries_;
    std::vector<int> result_, ancestor_;
    std::vector<char> color_;
    dsu d_;
};


#line 4 "test/tarjan_offline_lca.test.cpp"
#include <bits/stdc++.h>

int main() {
    std::cin.tie(0)->sync_with_stdio(0);
    int N, Q;
    std::cin >> N >> Q;
    std::vector<std::vector<int>> adj(N);
    for (auto i = 1; i < N; ++i) {
        int p;
        std::cin >> p;
        adj[p].push_back(i);
    }
    std::vector<std::pair<int, int>> queries(Q);
    for (auto &[u, v] : queries) {
        std::cin >> u >> v;
    }
    tarjan_offline_lca lca(adj, 0, queries);
    auto result = lca.lca();
    for (auto x : result) {
        std::cout << x << '\n';
    }
}

Back to top page