Test/LC/frequency_table_of_tree_distance.test.cpp

• View this file on GitHub
• Last update: 2024-12-06 16:40:42+09:00
• Problem: https://judge.yosupo.jp/problem/frequency_table_of_tree_distance

Depends on

• 木の重心 (Src/Graph/Tree/Centroid.hpp)
• ioまわりの設定 (Src/Template/IOSetting.hpp)
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/frequency_table_of_tree_distance"

#include "../../Src/Template/IOSetting.hpp"
#include "../../Src/Graph/Tree/Centroid.hpp"

#include <algorithm>
#include <iostream>
#include <vector>

using namespace zawa;

#include "atcoder/convolution"

int main() {
    SetFastIO();
    int N;
    std::cin >> N;
    std::vector<std::vector<int>> T(N);
    for (int i{} ; i < N - 1 ; i++) {
        int a, b;
        std::cin >> a >> b;
        T[a].push_back(b);
        T[b].push_back(a);
    }
    Centroid C(std::move(T));
    std::vector<int> dep(N);
    auto calc_dep{[&](auto dfs, int v, int p, int d) -> void {
        dep[v] = d;
        for (auto x : C[v]) if ((int)x != p and !C.isRemoved(x)) {
            dfs(dfs, x, v, d + 1);
        }
    }};
    std::vector<long long> ans(N);
    auto dfs{[&](auto dfs, int v) -> void {
        v = C.rooting(v);
        calc_dep(calc_dep, v, -1, 0);
        C.remove(v);
        std::vector<std::vector<int>> subtree;
        for (auto x : C.adjlist(v)) {
            subtree.push_back(C.component(x));
        }
        std::vector<long long> sq_sum, sum_sq;
        for (const auto& comp : subtree) {
            int max_d{};
            for (auto x : comp) max_d = std::max(max_d, dep[x]);
            std::vector<long long> cur(max_d + 1);
            for (auto x : comp) {
                ans[dep[x]]++; // vを端点としたパスの寄与
                cur[dep[x]]++;
            }
            while (sum_sq.size() < cur.size()) sum_sq.push_back(0LL);
            for (int i{} ; i < (int)cur.size() ; i++) {
                sum_sq[i] += cur[i];
            }
            cur = atcoder::convolution_ll(cur, cur);
            while (sq_sum.size() < cur.size()) sq_sum.push_back(0LL);
            for (int i{} ; i < (int)cur.size() ; i++) {
                sq_sum[i] += cur[i];
            }
        }
        sum_sq = atcoder::convolution_ll(sum_sq, sum_sq);
        for (int i{} ; i < (int)sum_sq.size() ; i++) {
            ans[i] += sum_sq[i] >> 1;
        }
        for (int i{} ; i < (int)sq_sum.size() ; i++) {
            ans[i] -= sq_sum[i] >> 1;
        }
        for (auto x : C.adjlist(v)) {
            dfs(dfs, x);
        }
    }};
    dfs(dfs, 0);
    for (int i{1} ; i < N ; i++) {
        std::cout << ans[i] << (i + 1 == N ? '\n' : ' ');
    }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/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 "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
    ~~~~~~~~~~~~~~^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 401, in update
    self.update(self._resolve(pathlib.Path(included), included_from=path))
                ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.13.5/x64/lib/python3.13/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 260, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: atcoder/convolution: line -1: no such header

Back to top page