VvyLw's Library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub

:heavy_check_mark: test/lca.test.cpp

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/lca"
#include "C++/graph/Graph.hpp"
#include "C++/graph/LCA.hpp"
int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);
    int n, q;
    std::cin >> n >> q;
    man::graph<false> g(n, 0);
    for(int i = 1; i < n; ++i) {
        int p;
        std::cin >> p;
        g.add(p, i);
    }
    man::LowestCommonAncestor lca(g);
    while(q--) {
        int u, v;
        std::cin >> u >> v;
        std::cout << lca.query(u, v) << '\n';
    }
}
#line 1 "test/lca.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lca"
#line 2 "C++/graph/Graph.hpp"

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#include <stack>

#include <ranges>

#ifndef TEMPLATE
namespace man {
template <class T, class U> constexpr inline bool chmin(T& a, const U& b) noexcept { if(a > b){ a = b; return true; } return false; }
}
#endif
#line 2 "C++/graph/edge.hpp"
#ifndef EDGE
#define EDGE
#endif

namespace man {
struct edge {
    int src, to, id;
    long long cost;
    edge(){}
    edge(const int src_, const int to_, const int id_ = -1, const long long cost_ = 0): src(src_), to(to_), id(id_), cost(cost_){}
    constexpr inline operator int() const noexcept { return to; }
};
}

/**
 * @brief Edge
 */
#line 15 "C++/graph/Graph.hpp"
namespace man {
template <bool undirected = true> struct graph: std::vector<std::vector<edge>> {
protected:
    int indexed, id;
    std::vector<edge> edges;
public:
    graph(){}
    graph(const int n, const int indexed_ = 1): indexed(indexed_), id(0){ this->resize(n); }
    inline void add(int a, int b) noexcept {
        a -= indexed, b-= indexed;
        (*this)[a].emplace_back(a, b, id);
        edges.emplace_back(a, b, id++);
        if(undirected) {
            (*this)[b].emplace_back(b, a, --id);
            edges.emplace_back(b, a, id++);
        }
    }
    inline void input(const int m) noexcept {
        for([[maybe_unused]] const auto _: std::views::iota(0, m)) {
            int a, b;
            std::cin >> a >> b;
            add(a, b);
        }
    }
    inline std::vector<edge> get_edge() const noexcept { return edges; }
    inline std::vector<int> all_dist(const int v) noexcept {
        std::vector<int> d(this -> size(), -1);
        std::queue<int> q;
        d[v] = 0;
        q.emplace(v);
        while(!q.empty()) {
            const int tmp = q.front();
            q.pop();
            for(const auto &el: (*this)[tmp]) {
                if(d[el] != -1) {
                    continue;
                }
                d[el] = d[tmp] + 1;
                q.emplace(el);
            }
        }
        return d;
    }
    inline int dist(const int u, const int v) noexcept { return all_dist(u)[v]; }
    inline std::vector<int> t_sort() noexcept {
        const int n = this->size();
		std::vector<int> deg(n);
		for(const auto i: std::views::iota(0, n)) {
			for(const auto ed: (*this)[i]) {
				deg[ed]++;
			}
		}
		std::stack<int> sk;
		for(const auto i: std::views::iota(0, n)) {
			if(deg[i] == 0) {
				sk.emplace(i);
			}
		}
		std::vector<int> ord;
		while(!sk.empty()) {
			const auto tmp = sk.top();
            sk.pop();
			ord.emplace_back(tmp);
			for(const auto ed: (*this)[tmp]) {
				if(--deg[ed] == 0) {
					sk.emplace(ed);
				}
			}
		}
		return ord.size() == size() ? ord : std::vector<int>{};
	}
    inline std::vector<edge> cycle() noexcept {
        const int n = size();
        std::vector<int> used(n);
        std::vector<edge> pre(n), cycle;
        const auto dfs = [&](const auto &f, const int i) -> bool {
            used[i] = 1;
			for(const auto &e: (*this)[i]) {
				if(used[e] == 0) {
					pre[e] = e;
					if(f(f, e)) {
						return true;
					}
				} else if(used[e] == 1) {
					int now = i;
					while(now != e) {
						cycle.emplace_back(pre[now]);
						now = pre[now].src;
					}
					cycle.emplace_back(e);
					return true;
				}
			}
			used[i] = 2;
			return false;
        };
        for(int i = 0; i < n; ++i) {
			if(used[i] == 0 && dfs(dfs, i)) {
				std::ranges::reverse(cycle);
				return cycle;
			}
		}
		return {};
    }
};
}

/**
 * @brief グラフライブラリ
 */
#line 2 "C++/graph/LCA.hpp"

#pragma GCC diagnostic ignored "-Wreorder"

#line 7 "C++/graph/LCA.hpp"
namespace man {
template <class G> struct LowestCommonAncestor {
private:
    const int LOG;
    std::vector<int> dep, sum;
    const G &g;
    std::vector<std::vector<int>> table;
    constexpr inline void dfs(const int idx, const int par, const int d) noexcept {
        table[0][idx] = par;
        dep[idx] = d;
        for(const auto &el: g[idx]) {
            if(el != par) {
                sum[el] = sum[idx] + el.cost;
                dfs(el, idx, d + 1);
            }
        }
    }
    constexpr inline void build() noexcept{
        dfs(0, -1, 0);
        for(const auto k: std::views::iota(0, LOG - 1)) {
            for(const auto i: std::views::iota(0, std::ssize(table[k]))) {
                if(table[k][i] == -1) {
                    table[k + 1][i] = -1;
                } else {
                    table[k + 1][i] = table[k][table[k][i]];
                }
            }
        }
    }
public:
    LowestCommonAncestor(const G &g_): g(g_), dep(std::ssize(g_)), sum(std::ssize(g_)), LOG(std::__lg(std::ssize(g_)) + 1) {
        table.assign(LOG, std::vector<int>(std::ssize(g_), -1));
        build();
    }
    constexpr inline int climb(int u, const int k) noexcept {
		if(dep[u] < k) {
			return -1;
		}
		for(const auto i: std::views::iota(0, LOG) | std::views::reverse) {
			if((k >> i) & 1) {
                u = table[i][u];
            }
		}
		return u;
	}
    constexpr inline int query(int u, int v) noexcept {
        if(dep[u] > dep[v]) {
            std::swap(u, v);
        }
        v = climb(v, dep[v] - dep[u]);
        if(u == v) {
            return u;
        }
        for(int i = LOG; --i >= 0;) {
            if(table[i][u] != table[i][v]) {
                u = table[i][u];
                v = table[i][v];
            }
        }
        return table[0][u];
    }
    constexpr inline int dist(const int u, const int v) const noexcept { return sum[u] + sum[v] - 2 * sum[query(u, v)]; }
};
}
/**
 * @brief Lowest Common Ancestor(最小共通祖先)
 * @docs docs/LCA.md
 * @see https://ei1333.github.io/luzhiled/snippets/tree/doubling-lowest-common-ancestor.html
 */
#line 4 "test/lca.test.cpp"
int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);
    int n, q;
    std::cin >> n >> q;
    man::graph<false> g(n, 0);
    for(int i = 1; i < n; ++i) {
        int p;
        std::cin >> p;
        g.add(p, i);
    }
    man::LowestCommonAncestor lca(g);
    while(q--) {
        int u, v;
        std::cin >> u >> v;
        std::cout << lca.query(u, v) << '\n';
    }
}
Back to top page