木 - 重心分解のテスト
(tests/graph.tree.centroid_decomposition.test.cpp)

• View this file on GitHub
• Last update: 2026-01-21 19:52:16+09:00
• Problem: https://judge.yosupo.jp/problem/frequency_table_of_tree_distance

Depends on

• 辺 (library/graph/base/edge.hpp)
• グラフ (library/graph/base/graph.hpp)
• 重心分解 (library/graph/tree/centroid_decomposition.hpp)
• 高速フーリエ変換 (library/polynomial/fft/fast_fourier_transform.hpp)
• テンプレート (template/template.hpp)

Code

#define PROBLEM                                                                \
    "https://judge.yosupo.jp/problem/frequency_table_of_tree_distance"
#include "template/template.hpp"
#include "library/graph/tree/centroid_decomposition.hpp"
#include "library/polynomial/fft/fast_fourier_transform.hpp"
/**
 * @brief 木 - 重心分解のテスト
 */
void solve() {
    int N;
    cin >> N;
    CentroidDecomposition g(N);
    g.read(N - 1, 0);
    int root = g.build();
    vector<int> used(N), dist(N);
    auto rec = [&](auto self, int centroid) -> void {
        used[centroid] = true;
        vector<int> cnt{1};
        for (auto &&edge : g.G[centroid]) {
            if (used[edge.to]) continue;
            vector<int> num;
            queue<tuple<int, int, int>> que;
            que.emplace(edge.to, centroid, 1);
            while (!que.empty()) {
                int idx, par, dep;
                tie(idx, par, dep) = que.front();
                que.pop();
                if ((int)cnt.size() <= dep) cnt.resize(dep + 1, 0);
                if ((int)num.size() <= dep) num.resize(dep + 1, 0);
                cnt[dep]++;
                num[dep]++;
                for (auto &&edge : g.G[idx]) {
                    if (edge.to == par or used[edge.to]) continue;
                    que.emplace(edge.to, idx, dep + 1);
                }
            }
            auto ret = FFT::multiply(num, num);
            for (int i = 0; i < (int)ret.size(); i++) dist[i] -= ret[i];
        }
        auto ret = FFT::multiply(cnt, cnt);
        for (int i = 0; i < (int)ret.size(); ++i) dist[i] += ret[i];
        for (auto &&[from, to, cost, idx] : g.tree.G[centroid]) self(self, to);
    };
    rec(rec, root);
    dist.erase(begin(dist));
    for (auto &&p : dist) p /= 2ll;
    print(dist);
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
  File "/home/runner/.local/lib/python3.12/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 400, in update
    raise BundleErrorAt(path, i + 1, "unable to process #include in #if / #ifdef / #ifndef other than include guards")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: template/template.hpp: line 7: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page