tree/test/lca.test.cpp

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

Depends on

• Lowest common ancestor （最小共通祖先） (tree/lowest_common_ancestor.hpp)

Code

#include "../lowest_common_ancestor.hpp"
#include <iostream>
#define PROBLEM "https://judge.yosupo.jp/problem/lca"
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, Q, p, u, v;
    cin >> N >> Q;
    UndirectedWeightedTree<int> graph(N);
    for (int i = 1; i <= N - 1; i++) {
        cin >> p;
        graph.add_edge(i, p, 1);
    }
    graph.fix_root(0);

    for (int i = 0; i < Q; i++) {
        cin >> u >> v;
        cout << graph.lowest_common_ancestor(u, v) << endl;
    }
}

#line 2 "tree/lowest_common_ancestor.hpp"
#include <utility>
#include <vector>

// CUT begin
// lowest common ancestor (LCA) for undirected weighted tree
template <typename T> struct UndirectedWeightedTree {
    int INVALID = -1;
    int V, lgV;
    int E;
    int root;
    std::vector<std::vector<std::pair<int, int>>> adj; // (nxt_vertex, edge_id)
    // vector<pint> edge; // edges[edge_id] = (vertex_id, vertex_id)
    std::vector<T> weight;     // w[edge_id]
    std::vector<int> par;      // parent_vertex_id[vertex_id]
    std::vector<int> depth;    // depth_from_root[vertex_id]
    std::vector<T> acc_weight; // w_sum_from_root[vertex_id]

    void _fix_root_dfs(int now, int prv, int prv_edge_id) {
        par[now] = prv;
        if (prv_edge_id != INVALID) acc_weight[now] = acc_weight[prv] + weight[prv_edge_id];
        for (auto nxt : adj[now])
            if (nxt.first != prv) {
                depth[nxt.first] = depth[now] + 1;
                _fix_root_dfs(nxt.first, now, nxt.second);
            }
    }

    UndirectedWeightedTree() = default;
    UndirectedWeightedTree(int N) : V(N), E(0), adj(N) {
        lgV = 1;
        while (1 << lgV < V) lgV++;
    }

    void add_edge(int u, int v, T w) {
        adj[u].emplace_back(v, E);
        adj[v].emplace_back(u, E);
        // edge.emplace_back(u, v);
        weight.emplace_back(w);
        E++;
    }

    std::vector<std::vector<int>> doubling;
    void _doubling_precalc() {
        doubling.assign(lgV, std::vector<int>(V));
        doubling[0] = par;
        for (int d = 0; d < lgV - 1; d++)
            for (int i = 0; i < V; i++) {
                if (doubling[d][i] == INVALID)
                    doubling[d + 1][i] = INVALID;
                else
                    doubling[d + 1][i] = doubling[d][doubling[d][i]];
            }
    }

    void fix_root(int r) {
        root = r;
        par.resize(V);
        depth.resize(V);
        depth[r] = 0;
        acc_weight.resize(V);
        acc_weight[r] = 0;
        _fix_root_dfs(root, INVALID, INVALID);
        _doubling_precalc();
    }

    int kth_parent(int x, int k) const {
        if (depth[x] < k) return INVALID;
        for (int d = 0; d < lgV; d++) {
            if (x == INVALID) return INVALID;
            if (k & (1 << d)) x = doubling[d][x];
        }
        return x;
    }

    int lowest_common_ancestor(int u, int v) const {
        if (depth[u] > depth[v]) std::swap(u, v);

        v = kth_parent(v, depth[v] - depth[u]);
        if (u == v) return u;
        for (int d = lgV - 1; d >= 0; d--) {
            if (doubling[d][u] != doubling[d][v]) u = doubling[d][u], v = doubling[d][v];
        }
        return par[u];
    }

    T path_length(int u, int v) const {
        // Not distance, but the sum of weights
        int r = lowest_common_ancestor(u, v);
        return (acc_weight[u] - acc_weight[r]) + (acc_weight[v] - acc_weight[r]);
    }

    int s_to_t_by_k_steps(int s, int t, int k) const {
        int l = lowest_common_ancestor(s, t);
        int dsl = depth[s] - depth[l], dtl = depth[t] - depth[l];
        if (k > dsl + dtl) {
            return INVALID;
        } else if (k < dsl) {
            return kth_parent(s, k);
        } else if (k == dsl) {
            return l;
        } else {
            return kth_parent(t, dsl + dtl - k);
        }
    }
};
#line 2 "tree/test/lca.test.cpp"
#include <iostream>
#define PROBLEM "https://judge.yosupo.jp/problem/lca"
using namespace std;

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);
    int N, Q, p, u, v;
    cin >> N >> Q;
    UndirectedWeightedTree<int> graph(N);
    for (int i = 1; i <= N - 1; i++) {
        cin >> p;
        graph.add_edge(i, p, 1);
    }
    graph.fix_root(0);

    for (int i = 0; i < Q; i++) {
        cin >> u >> v;
        cout << graph.lowest_common_ancestor(u, v) << endl;
    }
}

Back to top page