Static Top Tree + 木DP
(Src/Graph/Tree/DynamicTreeDP.hpp)

• View this file on GitHub
• Last update: 2025-12-03 17:47:01+09:00
• Include: #include "Src/Graph/Tree/DynamicTreeDP.hpp"

雛形

struct DP {
    using Vertex = ;
    using Edge = ;
    using PathCluster = ;
    using PointCluster = ;
    static PathCluster vertex(const Vertex&) {
    }
    static PathCluster addVertex(const PointCluster&, const Vertex&) {
    }
    static PointCluster addEdge(const PathCluster&, const Edge&) {
    }
    static PointCluster rake(const PointCluster, const PointCluster) {
    }
    static PathCluster compress(const PathCluster& p, const Edge& e, const PathCluster& c) {
    }
};

compressだけ引数の順番に注意。 $p$ が根に近いPath Cluster、 $c$ が根から離れたPath Cluster、 $e$ が間にあるHeavy Edgeに対応する。

struct Printer {
    void operator()(int v, string type, int par, DP::PathCluster p) const {
    }
    void operator()(int v, string type, int par, DP::PointCluster p) const {
    }
};

このoperator()を適切に定義し、Printerの実体をvisitメンバに与えるとStatic Top Treeのすべてのノードを出力する。

ノード番号は1-indexであり、葉側にあるノードほど頂点番号が小さい。

なので、DynamicTreeDPを使わずStaticTopTreeを用いてそのまま木dpなどを書くときは再帰をせずに $1$ から昇順にループを回せばよい。

• Antichainなどの子側のデータを保持しておく必要がない時にこのようなことをするかもしれない

ライブラリの使い方

DynamicTreeDP(const DynamicTreeDPGraph& g, usize root, std::vector<Vertex> vs, std::vector<Edge> es)

DynamicTreeDPGraphとはvector<vector<pair<usize, usize>>>である。いつもの隣接リストで、firstには接続先、secondには辺番号を収める。

子から親方向への辺が存在していれば良い。両方向に辺が張られていても問題なく動作する。

rootは根の頂点番号

vsは各頂点に対応する情報

esは各辺に対応する情報

他のメンバは実装見ればわかると思います。

Depends on

• Src/Graph/Tree/StaticTopTree.hpp
• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AtCoder/abc269_h.test.cpp
• Test/AtCoder/abc351_g.test.cpp
• Test/LC/point_set_tree_path_composite_sum_fixed_root.test.cpp

Code

#pragma once

#include "./StaticTopTree.hpp"

#include <concepts>
#include <variant>
// #include <iostream>

namespace zawa {

namespace concepts {

template <class T>
concept DynamicTreeDPInterface = requires {
    typename T::Vertex;
    typename T::Edge;
    typename T::PathCluster;
    typename T::PointCluster;
    { T::vertex(std::declval<typename T::Vertex>()) } -> std::same_as<typename T::PathCluster>;
    { T::addVertex(std::declval<typename T::PointCluster>(), std::declval<typename T::Vertex>()) } -> std::same_as<typename T::PathCluster>;
    { T::addEdge(std::declval<typename T::PathCluster>(), std::declval<typename T::Edge>()) } -> std::same_as<typename T::PointCluster>;
    { T::rake(std::declval<typename T::PointCluster>(), std::declval<typename T::PointCluster>()) } -> std::same_as<typename T::PointCluster>;
    { T::compress(std::declval<typename T::PathCluster>(), std::declval<typename T::Edge>(), std::declval<typename T::PathCluster>()) } -> std::same_as<typename T::PathCluster>;
};

} // namespace concepts

using DynamicTreeDPGraph = STTGraph;

template <concepts::DynamicTreeDPInterface T>
class DynamicTreeDP {
public:

    using Vertex = typename T::Vertex;

    using Edge = typename T::Edge;

    using Path = typename T::PathCluster;

    using Point = typename T::PointCluster;

private:

    using Item = std::variant<Path, Point>;

    static constexpr usize PathId = 0;

    static constexpr usize PointId = 1;

public:

    DynamicTreeDP() = default;

    DynamicTreeDP(const DynamicTreeDPGraph& g, usize root, std::vector<Vertex> vs, std::vector<Edge> es)
        : m_n{g.size()}, m_vs{vs}, m_es{es}, m_stt{g, root}, m_dp(m_stt.size()) {
        assert(g.size() == m_vs.size());
        assert(g.empty() or g.size() == m_es.size() + 1);
        for (usize i = 0 ; i < m_stt.size() ; i++)
            if (i != StaticTopTree::Empty)
                recalc(i);
        //std::cerr << "STT's Height is " << m_stt[m_stt.root()].height << std::endl;
    }

    inline usize size() const {
        return m_n;
    }

    Path operator()() const {
        return std::get<PathId>(m_dp[m_stt.root()]);
    }

    const Vertex& getVertex(usize v) const {
        assert(v < size());
        return m_vs[v];
    }

    void assignVertex(usize v, Vertex val) {
        assert(v < size());
        m_vs[v] = std::move(val);
        recalcAncestor(m_stt.posVertex(v));
    }

    const Edge& getEdge(usize e) const {
        assert(e < size());
        return m_es[e];
    }

    void assignEdge(usize e, Edge val) {
        assert(e < m_es.size());
        m_es[e] = std::move(val);
        recalcAncestor(m_stt.posEdge(e));
    }

    template <class F>
    void visit(F f) const {
        for (usize i = 0 ; i < m_stt.size() ; i++)
            if (i != StaticTopTree::Empty) {
                const auto& node = m_stt[i];
                std::string name = STTOpName(node.type);
                usize par = node.par;
                if (std::holds_alternative<Path>(m_dp[i]))
                    f(i, name, par, std::get<PathId>(m_dp[i]));
                else
                    f(i, name, par, std::get<PointId>(m_dp[i]));
            }
    }

private:

    usize m_n;

    std::vector<Vertex> m_vs;

    std::vector<Edge> m_es;

    StaticTopTree m_stt;

    std::vector<Item> m_dp;

    void recalc(usize i) {
        const StaticTopTree::Node& node = m_stt[i];
        switch (node.type) {
        case STTOp::Vertex:
        {
            const Vertex& v = m_vs[node.invV];
            m_dp[i] = Item{std::in_place_index<PathId>, T::vertex(v)};
            break;
        }
        case STTOp::AddVertex:
        {
            const Point& ch = std::get<PointId>(m_dp[node[0]]);
            const Vertex& v = m_vs[node.invV];
            m_dp[i] = Item{std::in_place_index<PathId>, T::addVertex(ch, v)};
            break;
        }
        case STTOp::AddEdge:
        {
            const Path& ch = std::get<PathId>(m_dp[node[0]]);
            const Edge& e = m_es[node.invE];
            m_dp[i] = Item{std::in_place_index<PointId>, T::addEdge(ch, e)};
            break;
        }
        case STTOp::Rake:
        {
            const Point& l = std::get<PointId>(m_dp[node[0]]);
            const Point& r = std::get<PointId>(m_dp[node[1]]);
            m_dp[i] = Item{std::in_place_index<PointId>, T::rake(l, r)};
            break;
        }
        case STTOp::Compress:
        {
            const Path& l = std::get<PathId>(m_dp[node[0]]);
            const Edge& e = m_es[node.invE];
            const Path& r = std::get<PathId>(m_dp[node[1]]);
            m_dp[i] = Item{std::in_place_index<PathId>, T::compress(l, e, r)};
            break;
        }
        default:
            break;
        }
    }

    void recalcAncestor(usize i) {
        for ( ; i != StaticTopTree::Empty ; i = m_stt[i].par)
            recalc(i);
    }

};

} // namespace zawa

#line 2 "Src/Graph/Tree/DynamicTreeDP.hpp"

#line 2 "Src/Graph/Tree/StaticTopTree.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Graph/Tree/StaticTopTree.hpp"

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
#include <string>
#include <tuple>

namespace zawa {

using STTGraph = std::vector<std::vector<std::pair<usize, usize>>>;

enum class STTOp {
    Vertex,
    AddVertex,
    AddEdge,
    Rake,
    Compress
};
std::string STTOpName(STTOp v) {
    static std::string name[]{"Vertex", "AddVertex", "AddEdge", "Rake", "Compress"};
    return name[static_cast<usize>(v)];
}

class StaticTopTree {
private:

    static constexpr u32 Bit = 30;
    
    static constexpr u32 Mask = (1 << Bit) - 1;

public:

    static constexpr usize Empty = 0;

    struct Node {
        STTOp type;
        usize par;
        u64 ch;
        usize invV, invE;
        usize height;
        inline usize operator[](usize i) const {
            assert(i < 2);
            return i ? (ch >> Bit) : (ch & Mask);
        }
    };

    StaticTopTree() = default;

    StaticTopTree(STTGraph g, usize root) 
        : m_g{move(g)}, m_nodes(1), m_posVertex(m_g.size(), Empty), m_posEdge(m_g.size(), Empty) {
        removeParent(root, Empty);
        hld(root);
        m_nodes.reserve(m_g.size() << 1);
        m_root = dfs(root);
    }

    inline usize size() const {
        return m_nodes.size();
    }

    inline usize root() const {
        return m_root;
    }

    const Node& operator[](usize i) const {
        assert(i < size());
        return m_nodes[i];
    }

    usize posVertex(usize v) const {
        assert(v < m_posVertex.size());
        return m_posVertex[v];
    }

    usize posEdge(usize e) const {
        assert(e < m_posEdge.size());
        return m_posEdge[e];
    }

private:

    STTGraph m_g;

    std::vector<Node> m_nodes;

    std::vector<usize> m_posVertex, m_posEdge;

    usize m_root;

    void removeParent(usize v, usize p) {
        for (usize i = 0 ; i + 1 < m_g[v].size() ; ) {
            if (m_g[v][i].first == p)
                swap(m_g[v][i], m_g[v].back());
            else
                removeParent(m_g[v][i++].first, v);
        }
        if (m_g[v].size()) {
            if (m_g[v].back().first == p)
                m_g[v].pop_back();
            else
                removeParent(m_g[v].back().first, v);
        }
    }

    usize hld(usize v) {
        if (m_g[v].empty())
            return 1;
        usize res = 1, mx = 0, arg = 0;
        for (usize i = 0 ; i < m_g[v].size() ; i++) {
            usize ch = hld(m_g[v][i].first);
            if (mx < ch) {
                arg = i;
                mx = ch;
            }
            res += ch;
        }
        if (arg)
            std::swap(m_g[v][0], m_g[v][arg]);
        return res;
    }

    usize makeNode(Node&& node) {
        const usize res = m_nodes.size();
        m_nodes.push_back(std::move(node));
        return res;
    }

    usize compressStrategy(const std::vector<std::pair<usize, usize>>& path) {
        assert(path.size());
        std::vector<std::tuple<usize, usize, usize>> stk;
        stk.reserve(path.size());
        auto merge = [&]() {
            auto [nr, vr, hr] = std::move(stk.back());
            stk.pop_back();
            auto [nl, vl, hl] = std::move(stk.back());
            stk.pop_back();
            usize e = m_g[vl][0].second;
            usize h = std::max(hl, hr) + 1;
            Node cur{STTOp::Compress, Empty, nl | (u64{nr} << Bit), Empty, e, h};
            usize merged = makeNode(std::move(cur));
            m_posEdge[e] = m_nodes[nl].par = m_nodes[nr].par = merged;
            stk.emplace_back(merged, vr, h);
        };
        for (auto [nd, v] : path) {
            stk.push_back({nd, v, m_nodes[nd].height});
            while (true) {
                usize len = stk.size();
                if (len >= 3 and (std::get<2>(stk[len - 3]) == std::get<2>(stk[len - 2]) or std::get<2>(stk[len - 3]) < std::get<2>(stk[len - 1]))) {
                    auto tmp = std::move(stk.back());
                    stk.pop_back();
                    merge();
                    stk.push_back(std::move(tmp));
                }
                else if (len >= 2 and std::get<2>(stk[len - 2]) <= std::get<2>(stk[len - 1]))
                    merge();
                else
                    break;
            }
        }
        while (stk.size() >= 2)
            merge();
        return std::get<0>(stk.back());
    }

    usize rakeStrategy(usize v, const std::vector<usize>& ch) {
        if (ch.empty()) {
            Node cur{STTOp::Vertex, Empty, 0, v, Empty, 0};
            return m_posVertex[v] = makeNode(std::move(cur));
        }
        std::vector<std::pair<usize, usize>> stk;
        auto merge = [&]() {
            auto [rnd, rh] = std::move(stk.back());
            stk.pop_back();
            auto [lnd, lh] = std::move(stk.back());
            stk.pop_back();
            usize h = std::max(lh, rh) + 1;
            Node cur{STTOp::Rake, Empty, lnd | (u64{rnd} << Bit), Empty, Empty, h};
            usize merged = makeNode(std::move(cur));
            stk.emplace_back(m_nodes[lnd].par = m_nodes[rnd].par = merged, h);
        };
        usize pd = [&]() -> usize {
            for (usize nd : ch) {
                stk.push_back({nd, m_nodes[nd].height});
                while (true) {
                    usize len = stk.size();
                    if (len >= 3 and (stk[len - 3].second == stk[len - 2].second or stk[len - 3].second < stk[len - 1].second)) {
                        auto tmp = std::move(stk.back());
                        stk.pop_back();
                        merge();
                        stk.push_back(std::move(tmp));
                    }
                    else if (len >= 2 and stk[len - 2].second <= stk[len - 1].second)
                        merge();
                    else
                        break;
                }
            }
            while (stk.size() >= 2)
                merge();
            return stk.back().first;
        }();
        Node cur{STTOp::AddVertex, Empty, pd, v, Empty, m_nodes[pd].height + 1};
        return m_posVertex[v] = m_nodes[pd].par = makeNode(std::move(cur));
    }

    usize dfs(usize v) {
        std::vector<std::pair<usize, usize>> path;
        for ( ; ; v = m_g[v][0].first) {
            path.emplace_back(dfsLight(v), v);
            if (m_g[v].empty())
                break;
        }
        return compressStrategy(path);
    }

    usize dfsLight(usize v) {
        std::vector<usize> chs;
        chs.reserve(m_g[v].size());
        for (usize i = 1 ; i < m_g[v].size() ; i++) {
            const auto [x, e] = m_g[v][i];
            const usize nd = dfs(x);
            Node cur{STTOp::AddEdge, Empty, nd, Empty, e, m_nodes[nd].height + 1};
            const usize ch = makeNode(std::move(cur));
            chs.push_back(m_posEdge[e] = m_nodes[nd].par = ch);
        }
        return rakeStrategy(v, chs);
    }
};

} // namespace zawa
#line 4 "Src/Graph/Tree/DynamicTreeDP.hpp"

#include <concepts>
#include <variant>
// #include <iostream>

namespace zawa {

namespace concepts {

template <class T>
concept DynamicTreeDPInterface = requires {
    typename T::Vertex;
    typename T::Edge;
    typename T::PathCluster;
    typename T::PointCluster;
    { T::vertex(std::declval<typename T::Vertex>()) } -> std::same_as<typename T::PathCluster>;
    { T::addVertex(std::declval<typename T::PointCluster>(), std::declval<typename T::Vertex>()) } -> std::same_as<typename T::PathCluster>;
    { T::addEdge(std::declval<typename T::PathCluster>(), std::declval<typename T::Edge>()) } -> std::same_as<typename T::PointCluster>;
    { T::rake(std::declval<typename T::PointCluster>(), std::declval<typename T::PointCluster>()) } -> std::same_as<typename T::PointCluster>;
    { T::compress(std::declval<typename T::PathCluster>(), std::declval<typename T::Edge>(), std::declval<typename T::PathCluster>()) } -> std::same_as<typename T::PathCluster>;
};

} // namespace concepts

using DynamicTreeDPGraph = STTGraph;

template <concepts::DynamicTreeDPInterface T>
class DynamicTreeDP {
public:

    using Vertex = typename T::Vertex;

    using Edge = typename T::Edge;

    using Path = typename T::PathCluster;

    using Point = typename T::PointCluster;

private:

    using Item = std::variant<Path, Point>;

    static constexpr usize PathId = 0;

    static constexpr usize PointId = 1;

public:

    DynamicTreeDP() = default;

    DynamicTreeDP(const DynamicTreeDPGraph& g, usize root, std::vector<Vertex> vs, std::vector<Edge> es)
        : m_n{g.size()}, m_vs{vs}, m_es{es}, m_stt{g, root}, m_dp(m_stt.size()) {
        assert(g.size() == m_vs.size());
        assert(g.empty() or g.size() == m_es.size() + 1);
        for (usize i = 0 ; i < m_stt.size() ; i++)
            if (i != StaticTopTree::Empty)
                recalc(i);
        //std::cerr << "STT's Height is " << m_stt[m_stt.root()].height << std::endl;
    }

    inline usize size() const {
        return m_n;
    }

    Path operator()() const {
        return std::get<PathId>(m_dp[m_stt.root()]);
    }

    const Vertex& getVertex(usize v) const {
        assert(v < size());
        return m_vs[v];
    }

    void assignVertex(usize v, Vertex val) {
        assert(v < size());
        m_vs[v] = std::move(val);
        recalcAncestor(m_stt.posVertex(v));
    }

    const Edge& getEdge(usize e) const {
        assert(e < size());
        return m_es[e];
    }

    void assignEdge(usize e, Edge val) {
        assert(e < m_es.size());
        m_es[e] = std::move(val);
        recalcAncestor(m_stt.posEdge(e));
    }

    template <class F>
    void visit(F f) const {
        for (usize i = 0 ; i < m_stt.size() ; i++)
            if (i != StaticTopTree::Empty) {
                const auto& node = m_stt[i];
                std::string name = STTOpName(node.type);
                usize par = node.par;
                if (std::holds_alternative<Path>(m_dp[i]))
                    f(i, name, par, std::get<PathId>(m_dp[i]));
                else
                    f(i, name, par, std::get<PointId>(m_dp[i]));
            }
    }

private:

    usize m_n;

    std::vector<Vertex> m_vs;

    std::vector<Edge> m_es;

    StaticTopTree m_stt;

    std::vector<Item> m_dp;

    void recalc(usize i) {
        const StaticTopTree::Node& node = m_stt[i];
        switch (node.type) {
        case STTOp::Vertex:
        {
            const Vertex& v = m_vs[node.invV];
            m_dp[i] = Item{std::in_place_index<PathId>, T::vertex(v)};
            break;
        }
        case STTOp::AddVertex:
        {
            const Point& ch = std::get<PointId>(m_dp[node[0]]);
            const Vertex& v = m_vs[node.invV];
            m_dp[i] = Item{std::in_place_index<PathId>, T::addVertex(ch, v)};
            break;
        }
        case STTOp::AddEdge:
        {
            const Path& ch = std::get<PathId>(m_dp[node[0]]);
            const Edge& e = m_es[node.invE];
            m_dp[i] = Item{std::in_place_index<PointId>, T::addEdge(ch, e)};
            break;
        }
        case STTOp::Rake:
        {
            const Point& l = std::get<PointId>(m_dp[node[0]]);
            const Point& r = std::get<PointId>(m_dp[node[1]]);
            m_dp[i] = Item{std::in_place_index<PointId>, T::rake(l, r)};
            break;
        }
        case STTOp::Compress:
        {
            const Path& l = std::get<PathId>(m_dp[node[0]]);
            const Edge& e = m_es[node.invE];
            const Path& r = std::get<PathId>(m_dp[node[1]]);
            m_dp[i] = Item{std::in_place_index<PathId>, T::compress(l, e, r)};
            break;
        }
        default:
            break;
        }
    }

    void recalcAncestor(usize i) {
        for ( ; i != StaticTopTree::Empty ; i = m_stt[i].par)
            recalc(i);
    }

};

} // namespace zawa

Back to top page