Skip to content

DSU on Tree

Introduction

What is a heuristic?

A heuristic is an optimization of an algorithm that rests on human experience and intuition.

The most familiar example is the small-to-large merging heuristic of a disjoint set union. The code looks like this:

1
2
3
4
5
6
void merge(int x, int y) {
  int xx = find(x), yy = find(y);
  if (size[xx] < size[yy]) swap(xx, yy);
  fa[yy] = xx;
  size[xx] += size[yy];
}

Here, given two sets of different sizes, we merge the smaller set into the larger one, not the larger into the smaller.

Why? The size of a set can be thought of as its height (under normal circumstances), and attaching the set of smaller height to the one of greater height clearly helps us find the parent.

This optimization, making the tree of smaller height a subtree of the taller one, is called small-to-large merging.

The algorithm

DSU on tree is an algorithm for certain offline problems on trees. It is at least as fast as most alternatives, and easier to understand and to implement.

Consider the following problem: Counting Distinct Colors on a Tree.

Motivating example

Given a tree with \(n\) nodes rooted at \(1\), in which node \(u\) has color \(c_u\), find for every node \(u\) how many distinct colors occur in the subtree rooted at \(u\).

\(n\le 2\times 10^5\).

dsu-on-tree-1.png

Problems like this are mostly solved with a heavy load of data structures (nested trees and the like). If the queries can be answered offline, is there a simpler way?

Procedure

Since we may work offline, let us precompute all the answers and then output each one in \(O(1)\).

Brute-force preprocessing takes \(O(n^2)\) time: it runs one traversal for every child node, each traversal is clearly of the same order of magnitude as \(n\), and there are \(n\) nodes, hence \(O(n^2)\).

The answer of a node is determined by its subtrees and the node itself. We will use this property to solve the problem.

First precompute the subtree size and the heavy child of every node. As in heavy-light decomposition, the heavy child is the child whose subtree has the most nodes. This clearly takes \(O(n)\).

Let \(cnt_i\) be the number of occurrences of color \(i\), and \(ans_u\) the answer for node \(u\).

To process a node \(u\), go through the following steps:

  1. First traverse the light (non-heavy) children of \(u\) and compute their answers, but do not keep their effect on the \(cnt\) array afterwards;
  2. traverse its heavy child and keep its effect on the \(cnt\) array;
  3. traverse the nodes in the subtrees of the light children of \(u\) once more and add their contributions, which gives the answer for \(u\).

dsu-on-tree-2.png

The figure above shows an example.

So for each node we traverse its heavy subtree once and its non-heavy subtrees twice, which is clearly the cheapest way.

Carrying out this procedure yields the answers for all subtrees of the node.

Why not merge steps 1 and 3? Because one \(cnt\) array cannot serve several subtrees at once, and more arrays would take too much space: everything has to fit in \(O(n)\) space.

Clearly, if a node \(u\) is traversed \(x\) times, then its heavy child is traversed \(x\) times and its light children (if it has any) \(2x\) times.

Note that \(cnt\) must be reset to zero after every traversal, except that of the heavy child.

Proof

Define heavy edges and light edges as in heavy-light decomposition (an edge to a heavy child is heavy, all the others are light). The figure below illustrates heavy children and heavy edges. For a tree with \(n\) nodes:

The path from the root to any node of the tree contains at most \(\log n\) light edges. Suppose there are \(x\) light edges between the root and the node, and let the subtree of the node have size \(y\). The child at the lower end of a light edge has a subtree less than half the size of its parent's (if it were more than half, the edge would not be light), so \(y<n/2^x\). Clearly \(n>2^x\), and therefore \(x<\log n\).

Moreover, if a node is the heavy child of its parent, its subtree is the largest among its siblings, so on the path from any node to the root, the parent at the upper end of a heavy edge never traverses this node while computing its answer. Hence the number of times a node is traversed equals the number of light edges on its path to the root, \(+1\) (the \(+1\) is there because the node itself has to be traversed). So this number is \(\le\log n+1\), the total time complexity is \(O(n(\log n+1))=O(n\log n)\), and outputting the answers costs \(O(m)\).

dsu-on-tree-3.png

The thick edges in the figure are heavy edges; the child at the lower end of a heavy edge is a heavy child

Optimization

As the proof pointed out, DSU on tree borrows the notions of heavy and light children from heavy-light decomposition to speed up merging. That being so, we can also use the DFS order produced by heavy-light decomposition directly, turn the recursion into iteration, and reduce the constant factor of DSU on tree further.

Any DFS order has the following property: the subtree of a node is contiguous in it. So we can scan the DFS order array backwards. This guarantees that when we reach a node, all the other nodes of its subtree have already been processed.

The DFS order produced by heavy-light decomposition has a further nice property: every heavy path is contiguous in it. So when we scan the nodes in reverse DFS order, the node visited right after the top of a heavy path is never the parent of that top node, so the effect of the top node has to be cleared. For a node that is not the top of a heavy path, on the other hand, the node visited just before it is either its own heavy child or a node of another branch whose effect has already been cleared, so the effect can simply be inherited. On top of that, use the DFS order to add the effect of all light children quickly, and record the answer.

This procedure is the non-recursive, or iterative, implementation of DSU on tree (also called its DFS-order implementation). Compared with the original recursive implementation, it saves the time and space overhead of recursive function calls, which is a considerable constant-factor optimization; on trees that contain many chain-like structures in particular, it has a marked advantage in stack space.

Implementation

Reference implementation
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cstdio>
#include <vector>
using namespace std;

constexpr int N = 2e5 + 5;

int n, m;

// g[u]: the nodes adjacent to u
vector<int> g[N];

// sz: subtree size
// big: heavy child
// col: color of the node
// L[u]: index of node u in the DFS order
// R[u]: largest DFS order index among the nodes in the subtree of u
// Node[i]: the node with DFS order index i
// totdfn: node counter, also the largest DFS order index visited so far
// ans: stores the answers
// cnt[i]: number of nodes with color i
// totColor: number of colors that occur at the moment
int sz[N], big[N], col[N], L[N], R[N], Node[N], totdfn;
int ans[N], cnt[N], totColor;

void add(int u) {
  if (cnt[col[u]] == 0) ++totColor;
  cnt[col[u]]++;
}

void del(int u) {
  cnt[col[u]]--;
  if (cnt[col[u]] == 0) --totColor;
}

int getAns() { return totColor; }

void dfs0(int u, int p) {
  L[u] = ++totdfn;
  Node[totdfn] = u;
  sz[u] = 1;
  for (int v : g[u])
    if (v != p) {
      dfs0(v, u);
      sz[u] += sz[v];
      if (!big[u] || sz[big[u]] < sz[v]) big[u] = v;
    }
  R[u] = totdfn;
}

void dfs1(int u, int p, bool keep) {
  // compute the answers of the light children
  for (int v : g[u])
    if (v != p && v != big[u]) {
      dfs1(v, u, false);
    }
  // compute the answer of the heavy child and keep the data computed on the way (to be inherited)
  if (big[u]) {
    dfs1(big[u], u, true);
  }
  for (int v : g[u])
    if (v != p && v != big[u]) {
      // the nodes of a subtree form a contiguous range of the DFS order, so we can iterate over it directly
      for (int i = L[v]; i <= R[v]; i++) {
        add(Node[i]);
      }
    }
  add(u);
  ans[u] = getAns();
  if (!keep) {
    for (int i = L[u]; i <= R[u]; i++) {
      del(Node[i]);
    }
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) scanf("%d", &col[i]);
  dfs0(1, 0);
  dfs1(1, 0, false);
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    int q;
    scanf("%d", &q);
    printf("%d\n", ans[q]);
  }
  return 0;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <cstdio>
#include <vector>
using namespace std;

constexpr int N = 2e5 + 5;

int n, m;

// g[u]: the nodes adjacent to u
vector<int> g[N];

// sz: subtree size
// son[u]: index of the heavy child of node u
// col: color of the node
// dfn[u]: index of node u in the DFS order
// bottom[u]: largest DFS order index among the nodes in the subtree of u
// totdfn: node counter, also the largest DFS order index visited so far
// fa[u]: index of the parent of node u
// top[u]: index of the top node of the heavy path containing node u
// rnk[i]: the node with DFS order index i
// ans[u]: stores the answer
// cnt[i]: number of nodes with color i
// totColor: number of colors that occur at the moment
int sz[N], son[N], col[N], dfn[N], fa[N], bottom[N], totdfn;
int top[N], rnk[N];
int ans[N], cnt[N], totColor;

void add(int u) {
  if (cnt[col[u]] == 0) ++totColor;
  cnt[col[u]]++;
}

void del(int u) {
  cnt[col[u]]--;
  if (cnt[col[u]] == 0) --totColor;
}

int getAns() { return totColor; }

void dfs0(int u, int p) {
  sz[u] = 1;
  fa[u] = p;
  for (int v : g[u])
    if (v != p) {
      dfs0(v, u);
      sz[u] += sz[v];
      if (!son[u] || sz[son[u]] < sz[v]) son[u] = v;
    }
}

void dfs1(int u, int t) {
  rnk[bottom[u] = dfn[u] = ++totdfn] = u;
  top[u] = t;
  if (!son[u]) return;
  dfs1(son[u], t);
  for (int v : g[u])
    if (v != fa[u] && v != son[u]) dfs1(v, v);
  bottom[u] = totdfn;
}

void dsu_on_tree() {
  for (int i = totdfn; i >= 1; i--) {
    int u = rnk[i];
    for (int v : g[u])
      if (v != fa[u] && v != son[u]) {
        for (int i = dfn[v]; i <= bottom[v]; i++) {
          add(rnk[i]);
        }
      }
    add(u);
    ans[u] = getAns();
    if (u == top[u]) {
      for (int i = dfn[u]; i <= bottom[u]; i++) {
        del(rnk[i]);
      }
    }
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) scanf("%d", &col[i]);
  dfs0(1, 1);
  dfs1(1, 1);
  dsu_on_tree();
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    int q;
    scanf("%d", &q);
    printf("%d\n", ans[q]);
  }
  return 0;
}

Applications

  1. Problems for which the problem setter's intended solution is DSU on tree

    One example is CF741D. Given a tree in which the weight of every node is a letter from 'a' to 'v', each query asks for a path inside a subtree such that the characters on the path can be rearranged into a palindrome.

    Since the palindrome is formed from a permutation of the characters, a character that occurs twice might as well not occur at all. In other words, the path has to satisfy that at most one character occurs an odd number of times.

    The straightforward approach runs a DFS from every node and, at each node it reaches, enumerates all letters by brute force to find the paths whose XOR with it has at most one bit equal to 1, then takes the longest. This is \(O(n^2\log n)\); DSU on tree brings it down to \(O(n\log^2n)\). For the details, see the further reading below.

  2. Problems where DSU on tree works as an ad hoc heuristic

    It can pick up partial scores on some nested-trees problems (those without updates), and its complexity beats the \(O(n\sqrt{m})\) of Mo's algorithm on trees.

Practice problems

CF600E Lomsat gelral

Problem summary: the nodes of a tree have colors, and a color dominates a subtree if and only if no other color occurs in that subtree more often than it does. For each subtree, find the sum of all colors that dominate it.

UOJ284 Happy Game Chicken

CF1709E XOR Tree

References and further reading

DSU on tree as introduced by the author of CF741D

That author's editorial