Dynamic Tree DP (tree/dynamic_tree_dp.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2025-09-26 12:25:37+07:00
Include: #include "tree/dynamic_tree_dp.hpp"

Description

If we define the process of computing tree DP as follow:

struct TreeDP {
  struct Info;
  struct Point;
  struct Path;
  fn vertex(Info v) -> Path;
  fn add_vertex(Point t, Info v) -> Path;
  fn add_edge(Path t) -> Point;
  fn compress(Path p, Path c) -> Path;
  fn rake(Point l, Point r) -> Point;
};

Point: Result of combining all light children of a vertex (Point cluster)
Path: Result of combining vertices connected by a heavy edge (Path cluster)
vertex(v): Creates a path cluster consisting of only vertex v
add_vertex(t, v): Sets v to be the root of point cluster t
add_edge(t): Add a virtual root to point cluster t to make it a path cluster
compress(p, c): Merge two path cluster p and c (p is closer to the root), it is usually sufficient to only consider the boundary vertices when merging
rake(l, r): Merge point clusters l and r

fn calc_light(int v) -> Point {
  vector<Point> points;
  // skip g[v][0] which is a heavy child
  for (int i = 1; i < g[v].size(); i++) {
    Path res = calc_heavy(g[v][i]);
    points.push_back(add_edge(res));
  }
  for (int i = 1; i < points.size(); i++) {
    points[0] = rake(points[0], points[i]);
  }
  return points[0];
}
fn calc_heavy(int v) -> Path {
  vector<Path> paths;
  while(!g[r].empty()) {
    if(g[r].size() == 1) {
      // no light children
      paths.push_back(vertex(info[r]));
    } else {
      // compute light edges
      Point res = calc_light(r);
      paths.push_back(add_vertex(res, info[r]));
    }
    r = g[r][0]; // traverse down to heavy child
  }
  for(int i = 1; i < (int) paths.size(); i++) {
    paths[0] = compress(paths[0], paths[i]);
  }
  return paths[0];
}

All that’s left is trying to balance a tree $T$ by binarizing it. This is done via Static Top Tree.

Operations

DDP(int n, STT &stt, TreeDP dp)
- Initialize the data structure
- Time complexity: $\mathcal O(n)$
void build()
- Computes DP using DPP::info (you set this manually)
- Time complexity: $\mathcal O(n)$
void pull_from(int v)
- Recomputes DP from vertex v
- Time complexity: $\mathcal O(\log n)$
void set(int v, const Info &x)
- Sets info[v] = x and recomputes DP from vertex v
- Time complexity: $\mathcal O(\log n)$
Path query()
- Returns DP result
- Time complexity: $\mathcal O(1)$

Verified with

test/yosupo/tree/point_set_tree_path_composite_sum_fixed_root.test.cpp

Code

#pragma once

template<class TreeDP, class STT> struct DDP {
    using Info = typename TreeDP::Info;
    using Point = typename TreeDP::Point;
    using Path = typename TreeDP::Path;

    STT &stt;
    int n, m, rt;
    vector<Info> info;
    vector<Point> point;
    vector<Path> path;

    void pull(int v) {
        if (stt[v].t == Vertex) {
            path[v] = TreeDP::vertex(info[v]);
        } else if (stt[v].t == AddVertex) {
            path[v] = TreeDP::add_vertex(point[stt[v].l], info[v]);
        } else if (stt[v].t == AddEdge) {
            point[v] = TreeDP::add_edge(path[stt[v].l]);
        } else if (stt[v].t == Compress) {
            path[v] = TreeDP::compress(path[stt[v].l], path[stt[v].r]);
        } else if (stt[v].t == Rake) {
            point[v] = TreeDP::rake(point[stt[v].l], point[stt[v].r]);
        }
    }

    DDP(int _n, STT &_stt, [[maybe_unused]] TreeDP _dp) :
        stt(_stt), n(_n), m(stt.size()), info(n), point(m), path(m) {}
    void build() {
        y_comb([&](auto &dfs, int v) -> void {
            if (stt[v].l != -1) dfs(stt[v].l);
            if (stt[v].r != -1) dfs(stt[v].r);
            pull(v);
        })(stt.rt);
    }
    void pull_from(int v) {
        for (; v != -1; v = stt[v].p) pull(v);
    }
    void set(int v, const Info &x) { info[v] = x, pull_from(v); }
    Path query() { return path[stt.rt]; }
};

#line 2 "tree/dynamic_tree_dp.hpp"

template<class TreeDP, class STT> struct DDP {
    using Info = typename TreeDP::Info;
    using Point = typename TreeDP::Point;
    using Path = typename TreeDP::Path;

    STT &stt;
    int n, m, rt;
    vector<Info> info;
    vector<Point> point;
    vector<Path> path;

    void pull(int v) {
        if (stt[v].t == Vertex) {
            path[v] = TreeDP::vertex(info[v]);
        } else if (stt[v].t == AddVertex) {
            path[v] = TreeDP::add_vertex(point[stt[v].l], info[v]);
        } else if (stt[v].t == AddEdge) {
            point[v] = TreeDP::add_edge(path[stt[v].l]);
        } else if (stt[v].t == Compress) {
            path[v] = TreeDP::compress(path[stt[v].l], path[stt[v].r]);
        } else if (stt[v].t == Rake) {
            point[v] = TreeDP::rake(point[stt[v].l], point[stt[v].r]);
        }
    }

    DDP(int _n, STT &_stt, [[maybe_unused]] TreeDP _dp) :
        stt(_stt), n(_n), m(stt.size()), info(n), point(m), path(m) {}
    void build() {
        y_comb([&](auto &dfs, int v) -> void {
            if (stt[v].l != -1) dfs(stt[v].l);
            if (stt[v].r != -1) dfs(stt[v].r);
            pull(v);
        })(stt.rt);
    }
    void pull_from(int v) {
        for (; v != -1; v = stt[v].p) pull(v);
    }
    void set(int v, const Info &x) { info[v] = x, pull_from(v); }
    Path query() { return path[stt.rt]; }
};