Guni (Sack) / DSU on tree （根付き木の全ての部分木を経由するような頂点追加・削除操作列の生成）
(tree/guni.hpp)

• View this file on GitHub
• Last update: 2026-04-19 01:24:04+09:00
• Include: #include "tree/guni.hpp"
• Link: https://atcoder.jp/contests/abc454/editorial/19112
• Link: https://codeforces.com/blog/entry/44351

できること

頂点数 $n$ の根付き木について，頂点集合の部分集合の列 $S = (S_0, \ldots, S_m)$ で，以下を満たすものを構築する．

• $S_0 = S_m = \emptyset$
• $| S_i \oplus S_{i + 1} | = 1$ （ $S_{i + 1}$ は $S_i$ から一個の頂点を追加または削除したもの）
• 各部分木について，それに含まれる頂点集合と $S_k$ が一致するような $k$ が存在する
• $m = O(n \log n)$

本コードはこのような $S$ の一つを implicit に構築する．根付き木の全ての部分木に関する特定の問題を全ての部分木に対して解く必要があるような状況で，効率的な実装に役立つ．

原理

木の上で DFS し，行きがけに頂点追加・帰りがけに頂点削除を行うのが基本方針だが，一部の頂点には複数回訪問する点で通常の DFS とは異なる．

Heavy-light decomposition を行う．ある頂点 $v$ に到達した際，以下の手続きを行う：

1. $v$ と light edge で繋がる子の部分木全てについて再帰的に DFS する
2. $v$ と heavy edge で繋がる子の部分木について再帰的に DFS する（ただし， 手順 6. の削除操作を省く）
3. $v$ light edge で繋がる子の部分木に含まれる全頂点を追加する
4. 頂点 $v$ を追加する
5. （ $S_v$ ができる）
6. $v$ の部分木に含まれる全頂点を削除する

このアルゴリズムは以下の背景により $O(n \log n)$ である：

• 手順 3. の計算量は weighted-union heuristic （いわゆるマージテク）により $O(n \log n)$ である．
• 各頂点が手順 6. で削除対象になる回数は，その頂点から根への単純パスに存在する（distinct な） heavy path の本数と一致するので， 6. の計算量は $O(n \log n)$ である．

使用方法

根付き木の全ての部分木について「部分木を構成する頂点の id の 2 乗和」は以下のように実装できる（本テクニックを使用するまでもない例だが）．

int N, root;
vector<pair<int, int>> edges(N - 1);

guni g(N);
for (auto [u, v] : edges) g.add_bi_edge(u, v);

std::vector<long long> ret(N);
long long sum_of_i_quads = 0;

auto Add = [&](int i) { sum_of_i_quads += (long long)i * i; };
auto ResetAll = [&](std::span<const int> view) {
    for (int i : view) sum_of_i_quads -= (long long)i * i;
};
auto Solve = [&](int i) { ret.at(i) = sum_of_i_quads; };

g.run(0, Add, ResetAll, Solve);

ResetAll は次のどちらでもよい．

• ResetAll(std::span<const int> view) : 削除すべき全頂点を受け取る
• ResetAll() : 何も受け取らない（全削除が $O(1)$ でできる場合など）

問題例

• Library Checker: Vertex Add Subtree Sum
• Codeforces Round 862 (Div. 2) E. There Should Be a Lot of Maximums
• AtCoder Beginner Contest 454 G - Mode in the Subtree

文献・リンク集

• [Tutorial] Sack (dsu on tree) - Codeforces
• DSU on Tree - Speaker Deck
• 解説 - キーサイト・テクノロジープログラミングコンテスト（AtCoder Beginner Contest 454）

Verified with

• tree/test/vertex-add-subtree-sum.guni.test.cpp

Code

#pragma once
#include <span>
#include <type_traits>
#include <vector>

// Guni / Sack / DSU on tree
// https://codeforces.com/blog/entry/44351
// https://atcoder.jp/contests/abc454/editorial/19112
struct guni {
    int n;
    int last_root;
    std::vector<std::vector<int>> to;
    std::vector<int> sz, ver, st, ft; // subtree size / dfs order / subtree start / subtree fin

    guni(int n_ = 0) : n(n_), last_root(-1), to(n_) {}

    void add_bi_edge(int u, int v) { to.at(u).push_back(v), to.at(v).push_back(u); }

    void sdfs(int v, int p) { // Build sz / ver / st / ft, and move heavy child to the back
        st.at(v) = ver.size(), ver.push_back(v);
        int heavy_idx = -1;
        for (int i = 0; i < int(to.at(v).size()); ++i) {
            int u = to.at(v).at(i);
            if (u == p) continue;
            sdfs(u, v);
            sz.at(v) += sz.at(u);
            if (heavy_idx == -1 or sz.at(u) > sz.at(to.at(v).at(heavy_idx))) heavy_idx = i;
        }
        if (heavy_idx != -1) std::swap(to.at(v).at(heavy_idx), to.at(v).back());
        ft.at(v) = ver.size();
    }

    std::span<const int> subtree(int v) const {
        return std::span<const int>(ver).subspan(st.at(v), ft.at(v) - st.at(v));
    }

    template <class F> void call_reset(F &ResetAll, int v) const {
        if constexpr (std::is_invocable_v<F &, std::span<const int>>) {
            ResetAll(subtree(v));
        } else {
            static_assert(
                std::is_invocable_v<F &>,
                "ResetAll must be callable with std::span<const int> or with no argument");
            ResetAll();
        }
    }

    template <class F1, class F2, class F3>
    void dfs(int v, int p, F1 &Add, F2 &ResetAll, F3 &Solve) {
        const int big_child = (!to.at(v).empty() and to.at(v).back() != p) ? to.at(v).back() : -1;
        for (int u : to.at(v)) {
            if (u != p and u != big_child) {
                dfs(u, v, Add, ResetAll, Solve);
                call_reset(ResetAll, u);
            }
        }
        if (big_child != -1) dfs(big_child, v, Add, ResetAll, Solve);

        for (int u : to.at(v)) {
            if (u != p and u != big_child) {
                for (int i = st.at(u); i < ft.at(u); ++i) Add(ver.at(i));
            }
        }
        Add(v);
        Solve(v);
    }

    template <class F1, class F2, class F3>
    void run(const int root, F1 Add, F2 ResetAll, F3 Solve) {
        if (last_root != root) {
            last_root = root, ver.clear(), st.resize(n), ft.resize(n), sz.assign(n, 1);
            sdfs(root, -1);
        }
        dfs(root, -1, Add, ResetAll, Solve);
        call_reset(ResetAll, root);
    }
};

#line 2 "tree/guni.hpp"
#include <span>
#include <type_traits>
#include <vector>

// Guni / Sack / DSU on tree
// https://codeforces.com/blog/entry/44351
// https://atcoder.jp/contests/abc454/editorial/19112
struct guni {
    int n;
    int last_root;
    std::vector<std::vector<int>> to;
    std::vector<int> sz, ver, st, ft; // subtree size / dfs order / subtree start / subtree fin

    guni(int n_ = 0) : n(n_), last_root(-1), to(n_) {}

    void add_bi_edge(int u, int v) { to.at(u).push_back(v), to.at(v).push_back(u); }

    void sdfs(int v, int p) { // Build sz / ver / st / ft, and move heavy child to the back
        st.at(v) = ver.size(), ver.push_back(v);
        int heavy_idx = -1;
        for (int i = 0; i < int(to.at(v).size()); ++i) {
            int u = to.at(v).at(i);
            if (u == p) continue;
            sdfs(u, v);
            sz.at(v) += sz.at(u);
            if (heavy_idx == -1 or sz.at(u) > sz.at(to.at(v).at(heavy_idx))) heavy_idx = i;
        }
        if (heavy_idx != -1) std::swap(to.at(v).at(heavy_idx), to.at(v).back());
        ft.at(v) = ver.size();
    }

    std::span<const int> subtree(int v) const {
        return std::span<const int>(ver).subspan(st.at(v), ft.at(v) - st.at(v));
    }

    template <class F> void call_reset(F &ResetAll, int v) const {
        if constexpr (std::is_invocable_v<F &, std::span<const int>>) {
            ResetAll(subtree(v));
        } else {
            static_assert(
                std::is_invocable_v<F &>,
                "ResetAll must be callable with std::span<const int> or with no argument");
            ResetAll();
        }
    }

    template <class F1, class F2, class F3>
    void dfs(int v, int p, F1 &Add, F2 &ResetAll, F3 &Solve) {
        const int big_child = (!to.at(v).empty() and to.at(v).back() != p) ? to.at(v).back() : -1;
        for (int u : to.at(v)) {
            if (u != p and u != big_child) {
                dfs(u, v, Add, ResetAll, Solve);
                call_reset(ResetAll, u);
            }
        }
        if (big_child != -1) dfs(big_child, v, Add, ResetAll, Solve);

        for (int u : to.at(v)) {
            if (u != p and u != big_child) {
                for (int i = st.at(u); i < ft.at(u); ++i) Add(ver.at(i));
            }
        }
        Add(v);
        Solve(v);
    }

    template <class F1, class F2, class F3>
    void run(const int root, F1 Add, F2 ResetAll, F3 Solve) {
        if (last_root != root) {
            last_root = root, ver.clear(), st.resize(n), ft.resize(n), sz.assign(n, 1);
            sdfs(root, -1);
        }
        dfs(root, -1, Add, ResetAll, Solve);
        call_reset(ResetAll, root);
    }
};

Back to top page