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

• View this file on GitHub
• Last update: 2026-01-21 19:52:16+09:00
• Problem: https://yukicoder.me/problems/no/1002

Depends on

• 辺 (library/graph/base/edge.hpp)
• グラフ (library/graph/base/graph.hpp)
• 重心分解 (library/graph/tree/centroid_decomposition.hpp)
• テンプレート (template/template.hpp)

Code

#define PROBLEM "https://yukicoder.me/problems/no/1002"
#include "template/template.hpp"
#include "library/graph/tree/centroid_decomposition.hpp"
/**
 * @brief 木 - 重心分解のテスト2
 */
void solve() {
    int N, K;
    cin >> N >> K;
    CentroidDecomposition G(N);
    G.read(N - 1, -1, true);
    int root = G.build();
    int ans = 0;
    vector<int> used(N);
    map<pair<int, int>, int> mp;
    int all;
    map<int, int> mp2, mp3;
    auto get_vec = [&](auto self, int idx, int par, int a, int b) -> void {
        if (!~b) {
            ans += all - mp2[a];
            ans += mp3[a];
        } else {
            ans++;
            ans += mp2[a] + mp2[b];
            ans += mp[minmax(a, b)];
        }
        for (auto &&e : G.G[idx]) {
            if (e.to == par) continue;
            if (used[e.to]) continue;
            if (a == e.cost) {
                self(self, e.to, idx, e.cost, b);
            } else if (!~b or b == e.cost) {
                self(self, e.to, idx, a, e.cost);
            }
        }
    };
    auto add_vec = [&](auto self, int idx, int par, int a, int b) -> void {
        if (!~b) {
            mp2[a]++;
            all++;
        } else {
            mp[minmax(a, b)]++;
            mp3[a]++;
            mp3[b]++;
        }
        for (auto &&e : G.G[idx]) {
            if (e.to == par) continue;
            if (used[e.to]) continue;
            if (a == e.cost) {
                self(self, e.to, idx, e.cost, b);
            } else if (!~b or b == e.cost) {
                self(self, e.to, idx, a, e.cost);
            }
        }
    };
    auto rec = [&](auto self, int idx) -> void {
        used[idx] = true;
        mp.clear();
        mp2.clear();
        mp3.clear();
        all = 0;
        for (auto &&e : G.G[idx]) {
            if (used[e.to]) continue;
            get_vec(get_vec, e.to, idx, e.cost, -1);
            add_vec(add_vec, e.to, idx, e.cost, -1);
        }
        for (auto &&e : G.tree.G[idx]) {
            self(self, e.to);
        }
        used[idx] = false;
    };
    rec(rec, root);
    print(ans);
}

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