graph/dynamic_tree_dp.hpp

• View this file on GitHub
• Last update: 2026-04-09 11:45:48+09:00
• Include: #include "graph/dynamic_tree_dp.hpp"

Depends on

• graph/graph.hpp
• graph/static_top_tree.hpp

Verified with

• graph/test/point_set_tree_path_composite_sum_fixed_root.test.cpp

Code

#pragma once
#include "static_top_tree.hpp"

template <typename TreeDP>
struct DynamicTreeDP {
    using Value = typename TreeDP::Value;
    using Func = typename TreeDP::Func;
    TreeDP &dp;
    StaticTopTree stt;
    std::vector<Value> value;
    std::vector<Func> func;
    template <typename T, bool DIR>
    DynamicTreeDP(Graph<T, DIR> &g, TreeDP &dp, int root = 0) : dp(dp), stt(g, root), value(stt.nodes.size()), func(stt.nodes.size()) {
        init(stt.stt_root);
    }
    Value update(int v) {
        while (v != -1) {
            update_single(v);
            v = stt.nodes[v].par;
        }
        return value[stt.stt_root];
    }
    Value get() const {
        return value[stt.stt_root];
    }

private:
    void init(int v) {
        const StaticTopTree::Node &node = stt.nodes[v];
        if (node.lch != -1) {
            init(node.lch);
        }
        if (node.rch != -1) {
            init(node.rch);
        }
        update_single(v);
    }
    void update_single(int v) {
        const StaticTopTree::Node &node = stt.nodes[v];
        if (node.ty == StaticTopTree::NodeType::AddEdge) {
            value[v] = dp.apply(func[node.lch], dp.id());
        } else if (node.ty == StaticTopTree::NodeType::AddVertex) {
            func[v] = dp.lift(v, node.lch == -1 ? dp.id() : value[node.lch]);
        } else if (node.ty == StaticTopTree::NodeType::Compress) {
            func[v] = dp.composite(func[node.lch], func[node.rch]);
        } else {
            value[v] = dp.op(value[node.lch], value[node.rch]);
        }
    }
};

#line 2 "graph/static_top_tree.hpp"
#include <algorithm>
#include <queue>
#line 2 "graph/graph.hpp"
#include <iostream>
#include <cassert>
#include <vector>
template <typename T>
struct Edge {
    using W = T;
    int from, to, id;
    W weight;
    Edge<T> rev() const {
        return Edge<T>{to, from, id, weight};
    }
};
template <typename T>
void debug(const Edge<T> &e) {
    std::cerr << e.from << " -> " << e.to << " id = " << e.id << std::cerr << " weight = ";
    debug(e.weight);
}
template <typename T = int, bool DIR = false>
class Graph {
public:
    using E = Edge<T>;
    using W = T;
    static constexpr bool DIRECTED = DIR;
    struct Adjacency {
        using Iter = typename std::vector<E>::iterator;
        Iter be, en;
        Iter begin() const { return be; }
        Iter end() const { return en; }
        int size() const { return (int)std::distance(be, en); }
        E &operator[](int idx) const { return be[idx]; }
    };
    struct ConstAdjacency {
        using Iter = typename std::vector<E>::const_iterator;
        Iter be, en;
        Iter begin() const { return be; }
        Iter end() const { return en; }
        int size() const { return (int)std::distance(be, en); }
        const E &operator[](int idx) const { return be[idx]; }
    };

private:
    int n, m;
    std::vector<E> edges, csr;
    std::vector<int> sep;
    bool built;

public:
    Graph(int n) : n(n), m(0), built(false) {}
    int v() const { return n; }
    int e() const { return m; }
    int add_vertex() {
        return n++;
    }
    void add_edge(int from, int to, W weight = 1) {
        assert(0 <= from && from < n && 0 <= to && to < n);
        edges.emplace_back(E{from, to, m++, weight});
    }
    void build() {
        sep.assign(n + 1, 0);
        csr.resize(DIRECTED ? m : 2 * m);
        for (const E &e : edges) {
            ++sep[e.from + 1];
            if (!DIRECTED) {
                ++sep[e.to + 1];
            }
        }
        for (int i = 0; i < n; ++i) {
            sep[i + 1] += sep[i];
        }
        std::vector<int> c = sep;
        for (const E &e : edges) {
            csr[c[e.from]++] = e;
            if (!DIRECTED) {
                csr[c[e.to]++] = e.rev();
            }
        }
        built = true;
    }
    Adjacency operator[](int v) {
        assert(built && 0 <= v && v < n);
        return Adjacency{csr.begin() + sep[v], csr.begin() + sep[v + 1]};
    }
    ConstAdjacency operator[](int v) const {
        assert(built && 0 <= v && v < n);
        return ConstAdjacency{csr.begin() + sep[v], csr.begin() + sep[v + 1]};
    }
};
#line 5 "graph/static_top_tree.hpp"

class StaticTopTree {
public:
    enum class NodeType {
        AddEdge,
        AddVertex,
        Compress,
        Rake
    };
    struct Node {
        NodeType ty;
        int par, lch, rch;
    };

    std::vector<Node> nodes;
    int stt_root;

    template <typename T, bool DIR>
    StaticTopTree(Graph<T, DIR> &g, int root = 0) {
        assert(0 <= root && root < g.v());
        nodes.reserve(3 * g.v());
        dfs(g, root, -1);
        nodes.resize(g.v(), Node{NodeType::AddVertex, -1, -1, -1});
        stt_root = compress(g, root, -1).second;
    }

private:
    template <typename T, bool DIR>
    int dfs(Graph<T, DIR> &g, int v, int p) {
        int sz = 1, mx = 0;
        for (Edge<T> &e : g[v]) {
            if (e.to == p) {
                continue;
            }
            int t = dfs(g, e.to, v);
            if (mx < t) {
                mx = t;
                swap(g[v][0], e);
            }
            sz += t;
        }
        return sz;
    }
    int make_node(NodeType ty, int lch, int rch) {
        int v = (int)nodes.size();
        nodes.emplace_back(Node{ty, -1, lch, rch});
        if (lch != -1) {
            nodes[lch].par = v;
        }
        if (rch != -1) {
            nodes[rch].par = v;
        }
        return v;
    }
    void merge(std::vector<std::pair<int, int>> &path) {
        auto [xf, xs] = path.back();
        path.pop_back();
        auto [yf, ys] = path.back();
        path.pop_back();
        path.emplace_back(std::max(xf, yf) + 1, make_node(NodeType::Compress, ys, xs));
    }
    template <typename T, bool DIR>
    std::pair<int, int> compress(const Graph<T, DIR> &g, int v, int p) {
        std::vector<std::pair<int, int>> path;
        while (true) {
            path.emplace_back(rake(g, v, p));
            while (true) {
                int l = (int)path.size();
                if (l >= 3 && (path[l - 3].first == path[l - 2].first || path[l - 3].first <= path[l - 1].first)) {
                    std::pair<int, int> t = path.back();
                    path.pop_back();
                    merge(path);
                    path.emplace_back(t);
                } else if (l >= 2 && path[l - 2].first <= path[l - 1].first) {
                    merge(path);
                } else {
                    break;
                }
            }
            if (g[v].size() == 0 || g[v][0].to == p) {
                break;
            }
            p = v;
            v = g[v][0].to;
        }
        while (path.size() >= 2) {
            merge(path);
        }
        auto [xf, xs] = path.back();
        int z = make_node(NodeType::AddEdge, xs, -1);
        return std::pair<int, int>(xf + 1, z);
    }
    template <typename T, bool DIR>
    std::pair<int, int> rake(const Graph<T, DIR> &g, int v, int p) {
        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<>> pq;
        for (int i = 1; i < (int)g[v].size(); ++i) {
            const Edge<T> &e = g[v][i];
            if (e.to == p) {
                continue;
            }
            pq.emplace(compress(g, e.to, v));
        }
        if (pq.empty()) {
            return std::pair<int, int>(0, v);
        }
        while (pq.size() >= 2) {
            auto [xf, xs] = pq.top();
            pq.pop();
            auto [yf, ys] = pq.top();
            pq.pop();
            pq.emplace(std::max(xf, yf) + 1, make_node(NodeType::Rake, xs, ys));
        }
        auto [rf, rs] = pq.top();
        nodes[v].lch = rs;
        nodes[rs].par = v;
        return std::pair<int, int>(rf + 1, v);
    }
};
#line 3 "graph/dynamic_tree_dp.hpp"

template <typename TreeDP>
struct DynamicTreeDP {
    using Value = typename TreeDP::Value;
    using Func = typename TreeDP::Func;
    TreeDP &dp;
    StaticTopTree stt;
    std::vector<Value> value;
    std::vector<Func> func;
    template <typename T, bool DIR>
    DynamicTreeDP(Graph<T, DIR> &g, TreeDP &dp, int root = 0) : dp(dp), stt(g, root), value(stt.nodes.size()), func(stt.nodes.size()) {
        init(stt.stt_root);
    }
    Value update(int v) {
        while (v != -1) {
            update_single(v);
            v = stt.nodes[v].par;
        }
        return value[stt.stt_root];
    }
    Value get() const {
        return value[stt.stt_root];
    }

private:
    void init(int v) {
        const StaticTopTree::Node &node = stt.nodes[v];
        if (node.lch != -1) {
            init(node.lch);
        }
        if (node.rch != -1) {
            init(node.rch);
        }
        update_single(v);
    }
    void update_single(int v) {
        const StaticTopTree::Node &node = stt.nodes[v];
        if (node.ty == StaticTopTree::NodeType::AddEdge) {
            value[v] = dp.apply(func[node.lch], dp.id());
        } else if (node.ty == StaticTopTree::NodeType::AddVertex) {
            func[v] = dp.lift(v, node.lch == -1 ? dp.id() : value[node.lch]);
        } else if (node.ty == StaticTopTree::NodeType::Compress) {
            func[v] = dp.composite(func[node.lch], func[node.rch]);
        } else {
            value[v] = dp.op(value[node.lch], value[node.rch]);
        }
    }
};

Back to top page