全方位木dp (lib/tree/rerooting.hpp)

• View this file on GitHub
• Last update: 2025-06-10 13:56:45+09:00
• Include: #include "lib/tree/rerooting.hpp"
• Link: https://algo-logic.info/tree-dp/

Depends on

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

Verified with

• test/aoj/challenge/3163.test.cpp
• test/yosupo/tree/tree_path_composite_sum.test.cpp

Code

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

/// @brief 全方位木dp
/// @see https://algo-logic.info/tree-dp/
template <class M, class T, class U>
struct ReRooting {
  private:
    using Value = typename M::value_type;

  public:
    ReRooting(const Graph<T> &g, const std::vector<U> &v)
        : graph(g), data(v), dp(g.size()), values(g.size()) {
        build();
    }

    const auto &operator[](int i) const { return values[i]; }
    auto &operator[](int i) { return values[i]; }
    const auto begin() const { return values.begin(); }
    auto begin() { return values.begin(); }
    const auto end() const { return values.end(); }
    auto end() { return values.end(); }

  private:
    Graph<T> graph;
    const std::vector<U> &data;
    std::vector<std::vector<Value>> dp;
    std::vector<Value> values;

    void build() {
        dfs(0);
        bfs(0);
    }

    Value dfs(int v, int p = -1) {
        Value res = M::id();
        int deg = graph[v].size();
        dp[v] = std::vector<Value>(deg, M::id());
        for (int i = 0; i < deg; ++i) {
            auto e = graph[v][i];
            if (e.to() == p) continue;
            dp[v][i] = M::f(dfs(e.to(), v), e.weight());
            res = M::op(res, dp[v][i]);
        }
        return M::g(res, data[v]);
    }
    void bfs(int v, int p = -1, Value dp_p = M::id()) {
        int deg = graph[v].size();
        std::vector<Value> dp_r(deg + 1, M::id());
        for (int i = deg - 1; i >= 0; --i) {
            auto e = graph[v][i];
            if (e.to() == p) dp[v][i] = M::f(dp_p, e.weight());
            dp_r[i] = M::op(dp[v][i], dp_r[i + 1]);
        }
        Value dp_l = M::id();
        for (int i = 0; i < deg; ++i) {
            int u = graph[v][i].to();
            if (u != p) bfs(u, v, M::g(M::op(dp_l, dp_r[i + 1]), data[v]));
            dp_l = M::op(dp_l, dp[v][i]);
        }
        values[v] = M::g(dp_l, data[v]);
    }
};

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