DSU on Tree(Guni)
(tree/dsu-on-tree.hpp)

View this file on GitHub
Last update: 2021-11-23 10:22:25+09:00
Include: #include "tree/dsu-on-tree.hpp"

DSU on Tree

DSU on Treeとは、全ての部分木に対するクエリを高速に処理するアルゴリズムである。

使い方&テンプレート

ライブラリと一緒に下のテンプレートを貼って使用する。

  // reflect data of node i
  auto update = [&](int i) {

  };
  // answer queries of subtree i
  auto query = [&](int i) {

  };
  // below two function are called if all data must be deleted
  // delete data of node i (if necesarry)
  auto clear = [&](int i) {

  };
  // delete data related to all (if necesarry)
  auto reset = [&]() {

  };
  DSUonTree<decltype(g)> dsu(g, 0);
  dsu.run(update, query, clear, reset);

概要

前に手元のメモに書いた落書きを貼る。

参考にしたサイト

説明

Python風コードによるアルゴリズムの動作の説明を以下に示す。

# c ... current node
# p ... parent node
# keep ... condition variable of reserving data

def dsu(c, p, keep):
    # light edge -> run dfs and clear data
    for d in 'light edge of c':
        dsu(d, c, false)
    
    # heavy edge -> run dfs and reserve data
    dsu('heavy edge of c', c, true)
    
    # light edge -> reserve data
    for d in 'light edge of c':
        for n in 'subtree of d':
            add(n)
     
    # current node -> reserve data
    add(c)

    # answer queries related to subtree of current node
    query(c)

    # if keep is false, clear all data
    if keep = false:
          reset()
    return

計算量

add()を呼び出す回数を考える
各ノードがaddされる回数を考えるとそれぞれ$\rm O(\log N)$回
- 全てのノードがdsu関数を1回ずつ実行
- 関数内ではlight edgeでつながる子孫 + 自分をaddしている
- よってノードがaddされる回数は$($根とのパスに存在するlight edgeの本数 + $1)$回
- 重軽木の深さは$\rm O(\log N)$なので回数も同じ
eraseされる回数はaddされる回数と同じ
以上より、全体の計算量はadd,eraseを$\rm O(1)$として$\rm O(N \log N)$

DSU on TreeとWeighted Union Heuristic(マージテク)の違い

Weighted Union Heuristic…競プロで広く一般に使われるテクニック
大きい部分木を小さい部分木にマージすることで$\rm{O}(N \log N)$
例えば下のような問題

頂点$1$を根とする$N$頂点の根付き木がある。木の頂点には数字$(1 \leq c \leq N)$が書かれている。次のオフラインクエリを$Q$個処理せよ。 $n\ x \ldots$ 頂点$n$を根とする部分木の全ての頂点のうち$x$の書かれた頂点の個数を出力。

これはマージテクだと$\rm{O}(N \log N)$で解ける(実装も簡単だが、hash tableが必要)
- DSU on Treeだと配列のみで$\rm O(N \log N)$が達成できる
- 類題

int a[N]; // number of nodes
using M = unordered_map<int, int>;
M dp[N];

void merge(M &a, M &b) {
    if (a.size() < b.size()) swap(a, b);
    for (auto &x : b) a[x.first] += x.second;
}

void dfs(int c, int p) {
    dp[c][a[c]] += 1;
    for (auto &d : g[c]){
        if (d == p) continue;
        dfs(d, c);
        merge(dp[c], dp[d]);
    }
    // answer queries of subtree c
}

ではこの問題は？

頂点$1$を根とする$N$頂点の根付き木がある。木の頂点には数字$(1 \leq c \leq N)$が書かれている。次のクエリを$Q$個処理せよ。 $n\ x\ \ldots$ 頂点$n$を根とする部分木の全ての頂点のうち$x$以下の書かれた頂点個数を出力。制約：$1 \leq N = Q \leq 200000$

これをマージテクで解こうとすると…?

hash mapをマージ

クエリが$\rm{O}($要素数$)$になり壊れる

vectorをマージ(クエリを二分探索で処理)

マージが$\rm{O}($小さい方$)$にならない

Segment Treeをノードごとに構築、一方hash mapでも頂点を管理 hash mapをマージする時に小さい方のデータを大きい方のセグ木に反映

一見うまくいきそうだが…

セグ木の構築にノードごとに$\rm{O}(N)$かかるので最悪$\rm O(N^2)$

動的Segment Treeや平衡二分木をマージ

構築ノードごとに$\rm{O}(1)$か$\rm{O}(\log N)$

マージ全体で$\rm{O}(N \log ^ 2 N)$

クエリクエリごとに$\rm{O}(\log N)$

よって高速に動作する

ただし、最悪ケースで$\rm{O}(N)$個のセグ木が同時に構築される

Heavy Light Decomposition + 4.の解法

heavyな部分木から動的セグ木を参照渡しでもらう

同時に構築される動的セグ木の数は$\rm{O}(\log N)$個となり空間計算量が改善された

一方、DSU on Treeだとセグメント木1本で解ける(計算量は$\rm O(N \log ^2 N)$)
- なおこの問題はEuler Tour + 領域木で$\rm{O}(N \log N)$と高速かつオンラインで解ける
- 動的木のマージも実は工夫すると全体で$\rm O(N \log N)$らしい (参考)のでマージテク+永続セグ木でも$\rm O(N \log N)$か
DSU on Treeのメリット
- データ構造が一つでいい
  - メモリ確保の回数や空間計算量少ない分、高速なことが多いらしい(要出典)
- ライブラリ化できる
  - 実装の手間が省けてありがたい
DSU on Treeのデメリット
- 値の追加だけでなく削除ができる必要がある
- 削除が面倒な例: priority_queue
  - 初期状態に戻せば問題ないので、例えば auto clear=[&](){}; auto reset=[&](){Q.swap(priority_queue<int>());}; のようにすればよいが、1個のデータ構造で出来るというメリットが失われている
疑問：DSU on Treeで解けてマージテクで解けない問題(あるいはその逆)は存在するのか？
- 存在しない気がする
- それはそれとしてDSU on Treeの方が(ライブラリがあれば)簡単に書けそう
- 親に返す時に操作が必要な場合は上記のライブラリでは対応できない？

Depends on

グラフテンプレート (graph/graph-template.hpp)

Verified with

Code

#pragma once



#include "../graph/graph-template.hpp"

template <typename G>
struct DSUonTree {
 private:
  G &g;
  int N;
  vector<int> sub_sz, euler, down, up;
  int idx_;
  int root;

  int dfs1(int cur, int par = -1) {
    sub_sz[cur] = 1;
    if ((int)g[cur].size() >= 2 and g[cur][0] == par) {
      swap(g[cur][0], g[cur][1]);
    }
    for (auto &dst : g[cur]) {
      if (dst == par) continue;
      sub_sz[cur] += dfs1(dst, cur);
      if (sub_sz[dst] > sub_sz[g[cur][0]]) swap(dst, g[cur][0]);
    }
    return sub_sz[cur];
  }

  void dfs2(int cur, int par = -1) {
    euler[idx_] = cur;
    down[cur] = idx_++;
    for (auto &dst : g[cur]) {
      if (dst == par) continue;
      dfs2(dst, cur);
    }
    up[cur] = idx_;
  }

 public:
  DSUonTree(G &_g,int _root = 0)
      : g(_g),
        N(_g.size()),
        sub_sz(_g.size()),
        euler(_g.size()),
        down(_g.size()),
        up(_g.size()),
        idx_(0),
        root(_root) {
    dfs1(root);
    dfs2(root);
  }

  int idx(int u) const { return down[u]; }

  template <typename UPDATE, typename QUERY, typename CLEAR, typename RESET>
  void run(UPDATE &update, QUERY &query, CLEAR &clear, RESET &reset) {
    auto dsu = [&](auto rc, int cur, int par = -1, bool keep = false) -> void {
      for (int i = 1; i < (int)g[cur].size(); i++)
        if (g[cur][i] != par) rc(rc, g[cur][i], cur, false);
      if (sub_sz[cur] != 1) rc(rc, g[cur][0], cur, true);
      if (sub_sz[cur] != 1)
        for (int i = up[g[cur][0]]; i < up[cur]; i++) update(euler[i]);
      update(cur);
      query(cur);
      if (!keep) {
        for (int i = down[cur]; i < up[cur]; i++) clear(euler[i]);
        reset();
      }
      return;
    };
    dsu(dsu, root);
  }
};

/**
 * @brief DSU on Tree(Guni)
 * @docs docs/tree/dsu-on-tree.md
 */

#line 2 "tree/dsu-on-tree.hpp"



#line 2 "graph/graph-template.hpp"

template <typename T>
struct edge {
  int src, to;
  T cost;

  edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
  edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
                      bool is_1origin = true) {
  UnweightedGraph g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    if (is_1origin) x--, y--;
    g[x].push_back(y);
    if (!is_directed) g[y].push_back(x);
  }
  return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
                        bool is_1origin = true) {
  WeightedGraph<T> g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    cin >> c;
    if (is_1origin) x--, y--;
    g[x].emplace_back(x, y, c);
    if (!is_directed) g[y].emplace_back(y, x, c);
  }
  return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) {
  Edges<T> es;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
                           bool is_directed = false, bool is_1origin = true) {
  vector<vector<T>> d(N, vector<T>(N, INF));
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */
#line 6 "tree/dsu-on-tree.hpp"

template <typename G>
struct DSUonTree {
 private:
  G &g;
  int N;
  vector<int> sub_sz, euler, down, up;
  int idx_;
  int root;

  int dfs1(int cur, int par = -1) {
    sub_sz[cur] = 1;
    if ((int)g[cur].size() >= 2 and g[cur][0] == par) {
      swap(g[cur][0], g[cur][1]);
    }
    for (auto &dst : g[cur]) {
      if (dst == par) continue;
      sub_sz[cur] += dfs1(dst, cur);
      if (sub_sz[dst] > sub_sz[g[cur][0]]) swap(dst, g[cur][0]);
    }
    return sub_sz[cur];
  }

  void dfs2(int cur, int par = -1) {
    euler[idx_] = cur;
    down[cur] = idx_++;
    for (auto &dst : g[cur]) {
      if (dst == par) continue;
      dfs2(dst, cur);
    }
    up[cur] = idx_;
  }

 public:
  DSUonTree(G &_g,int _root = 0)
      : g(_g),
        N(_g.size()),
        sub_sz(_g.size()),
        euler(_g.size()),
        down(_g.size()),
        up(_g.size()),
        idx_(0),
        root(_root) {
    dfs1(root);
    dfs2(root);
  }

  int idx(int u) const { return down[u]; }

  template <typename UPDATE, typename QUERY, typename CLEAR, typename RESET>
  void run(UPDATE &update, QUERY &query, CLEAR &clear, RESET &reset) {
    auto dsu = [&](auto rc, int cur, int par = -1, bool keep = false) -> void {
      for (int i = 1; i < (int)g[cur].size(); i++)
        if (g[cur][i] != par) rc(rc, g[cur][i], cur, false);
      if (sub_sz[cur] != 1) rc(rc, g[cur][0], cur, true);
      if (sub_sz[cur] != 1)
        for (int i = up[g[cur][0]]; i < up[cur]; i++) update(euler[i]);
      update(cur);
      query(cur);
      if (!keep) {
        for (int i = down[cur]; i < up[cur]; i++) clear(euler[i]);
        reset();
      }
      return;
    };
    dsu(dsu, root);
  }
};

/**
 * @brief DSU on Tree(Guni)
 * @docs docs/tree/dsu-on-tree.md
 */

Nyaan's Library

This documentation is automatically generated by online-judge-tools/verification-helper

DSU on Tree(Guni)
(tree/dsu-on-tree.hpp)

DSU on Tree

使い方&テンプレート

概要

参考にしたサイト

説明

計算量

DSU on TreeとWeighted Union Heuristic(マージテク)の違い

Depends on

Verified with

Code

DSU on Tree(Guni) (tree/dsu-on-tree.hpp)

DSU on Tree

使い方&テンプレート

概要

参考にしたサイト

説明

計算量

DSU on TreeとWeighted Union Heuristic(マージテク)の違い

Depends on

Verified with

Code

DSU on Tree(Guni)
(tree/dsu-on-tree.hpp)