木の距離を求める (lib/tree/tree_function.hpp)

• View this file on GitHub
• Last update: 2025-06-10 13:56:45+09:00
• Include: #include "lib/tree/tree_function.hpp"

Depends on

• 重み付きグラフ (lib/graph/graph.hpp)

Verified with

• test/aoj/jag/aho_corasick.test.cpp
• test/yosupo/tree/tree_diameter.test.cpp

Code

#pragma once
#include <stack>
#include <vector>
#include "graph/graph.hpp"

template <class T>
std::vector<int> tree_bfs(const Graph<T> &g, int r = 0) {
    int pos = 0;
    std::vector<int> res;
    std::vector<bool> visited(g.size());
    res.emplace_back(r);
    visited[r] = true;
    while (pos < (int)res.size()) {
        auto index = res[pos++];
        for (auto &e : g[index]) {
            if (visited[e.to()]) continue;
            res.emplace_back(e.to());
            visited[e.to()] = true;
        }
    }
    return res;
}

std::vector<int> tree_bfs(const std::vector<int> &parents) {
    int n = parents.size();
    Graph<void> g(n);
    int r = 0;
    for (int i = 0; i < n; ++i) {
        if (parents[i] == -1 || parents[i] == i) {
            r = i;
            continue;
        }
        g.add_edges(i, parents[i]);
    }
    return tree_bfs(g, r);
}

template <class T>
std::vector<int> tree_dfs(const Graph<T> &g, int r = 0) {
    std::vector<int> res;
    auto dfs = [&g, &res](auto self, int index, int parent) -> void {
        res.emplace_back(index);
        for (auto &e : g[index]) {
            if (e.to() == parent) continue;
            self(self, e.to(), index);
        }
    };
    dfs(dfs, r, -1);
    return res;
}

/// @brief 木の距離を求める
template <class T, class U = T>
std::vector<U> tree_dist(const Graph<T> &g, int r = 0) {
    std::vector<U> res(g.size(), -1);
    std::stack<int> st;
    res[r] = 0;
    st.emplace(r);
    while (!st.empty()) {
        auto index = st.top();
        st.pop();
        for (auto &e : g[index]) {
            if (res[e.to()] != -1) continue;
            res[e.to()] = res[index] + e.weight();
            st.emplace(e.to());
        }
    }
    return res;
}

/// @brief 木の頂点の親を求める
template <class T>
std::vector<int> tree_parent(const Graph<T> &g, int r = 0) {
    std::vector<int> res(g.size(), -1);
    std::stack<int> st;
    res[r] = r;
    st.emplace(r);
    while (!st.empty()) {
        auto index = st.top();
        st.pop();
        for (auto &e : g[index]) {
            if (res[e.to()] != -1) continue;
            res[e.to()] = index;
            st.emplace(e.to());
        }
    }
    res[r] = -1;
    return res;
}

/// @brief 部分木の大きさを求める
template <class T>
std::vector<int> tree_subtree(const Graph<T> &g, int r = 0) {
    std::vector<int> res(g.size());
    auto dfs = [&g, &res](auto self, int index) -> int {
        res[index] = 1;
        for (auto &e : g[index]) {
            if (res[e.to()] != 0) continue;
            res[index] += self(self, e.to());
        }
        return res[index];
    };
    dfs(dfs, r);
    return res;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: graph/graph.hpp: line -1: no such header

Back to top page