Skip to content

Tree Decomposition

Methods of Tree Decomposition

You can refer to True - Mo's Algorithm on Tree.

You can also refer to ouuan's blog / Detailed Explanation of Mo's Algorithm, Mo's Algorithm with Modifications, Mo's Algorithm on Tree / Mo's Algorithm on Tree.

Mo's Algorithm on Tree can also refer to the above two articles.

Applications of Tree Decomposition

Besides being applied to Mo's Algorithm, tree decomposition can be flexibly used in certain tree problems. However, problems that can be solved by tree decomposition often have better alternative approaches, so there are relatively few related problems.

By the way, the tree decomposition solution for "gty's sister tree" can be countered by a star graph.

BZOJ4763 Snow Radiance

First, perform tree decomposition. Then, for each key point in every block, precompute the bitset of colors on the path from it to each key point among its ancestors, as well as the nearest key point ancestor for each key point. The complexity is \(O(n\sqrt n+\frac{nc}{32})\), where \(n\sqrt n\) is the complexity of brute-force jumping upward from each key point, and \(\frac{nc}{32}\) is the complexity of storing \(O(n)\) bitsets.

When answering queries, first brute-force jump from the endpoints of the path to the key points of their respective blocks. Then jump upward block by block from the key points of the blocks until reaching the block containing the LCA, and finally brute-force jump to the LCA. The bitsets between key points are already precomputed, and the remaining parts are computed during the brute-force jumps. The complexity per query is \(O(\sqrt n+\frac c{32})\), where \(\sqrt n\) is the complexity of brute-force jumps within blocks and jumps between blocks, and \(O(\frac c{32})\) is the complexity of merging the precomputed results with the brute-force results. Counting the number of colors can be done using bitset's count(), and finding \(\operatorname{mex}\) can be done using bitset's _Find_first().

Thus, the total complexity is \(O((n+m)(\sqrt n+\frac c{32}))\).

Reference Code 

  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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
```cpp
#include <bitset>
#include <cctype>
#include <iostream>

#if defined(_MSC_VER) && !defined(__clang__)
#include <immintrin.h>
#endif

using namespace std;

constexpr int N = 100010;
constexpr int B = 666;
constexpr int C = 30000;

void add(int u, int v);
void dfs(int u);

int head[N], nxt[N << 1], to[N << 1], cnt;
int n, m, type, c[N], fa[N], dep[N], sta[N], top, tot, bl[N], key[N / B + 5],
    p[N], keyid[N];
bool vis[N];
bitset<C> bs[N / B + 5][N / B + 5], temp;

template <size_t N>
size_t find_first(std::bitset<N> b) {
#if defined(__GNUC__) && !defined(__clang__)
  return b._Find_first();
#elif defined(_MSC_VER) && !defined(__clang__)
  using word_t = decltype(b._Getword(0));
  constexpr ptrdiff_t word_len = CHAR_BIT * sizeof(word_t);
  constexpr ptrdiff_t words = N == 0 ? 0 : (N - 1) / word_len;
  size_t ans = 0;
  for (size_t i = 0; i <= words; ++i)
    if (b._Getword(i) != 0) {
      if (sizeof(word_t) == sizeof(unsigned int))
        return i * word_len + _tzcnt_u32(b._Getword(i));
      else
        return i * word_len + _tzcnt_u64(b._Getword(i));
    }
  return N;
#else
  auto s = b.to_string();
  for (size_t i = s.size() - 1; ~i; --i)
    if (s[i] & 1) return s.size() - 1 - i;
  return N;
#endif
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int i, u, v, x, y, k, lastans = 0;
  cin >> n >> m >> type;

  for (i = 1; i <= n; ++i) cin >> c[i];

  for (i = 1; i < n; ++i) {
    cin >> u >> v;
    add(u, v);
    add(v, u);
  }

  dfs(1);

  if (!tot) ++tot;
  if (keyid[key[tot]] == tot) keyid[key[tot]] = 0;
  key[tot] = 1;
  keyid[1] = tot;
  while (top) bl[sta[top--]] = tot;

  for (i = 1; i <= tot; ++i) {  // Preprocessing
    if (vis[key[i]]) continue;
    vis[key[i]] = true;
    temp.reset();
    for (u = key[i]; u; u = fa[u]) {
      temp[c[u]] = 1;
      if (keyid[u]) {
        if (!p[key[i]] && u != key[i]) p[key[i]] = u;
        bs[keyid[key[i]]][keyid[u]] = temp;
      }
    }
  }

  while (m--) {
    cin >> k;
    temp.reset();
    while (k--) {
      cin >> x >> y;
      u = x ^= lastans;
      v = y ^= lastans;

      while (key[bl[x]] != key[bl[y]]) {
        if (dep[key[bl[x]]] > dep[key[bl[y]]]) {
          if (x == u) {  // If it's the first jump, brute force to the key point
            while (x != key[bl[u]]) {
              temp[c[x]] = 1;
              x = fa[x];
            }
          } else
            x = p[x];  // Otherwise, jump a whole block
        } else {
          if (y == v) {
            while (y != key[bl[v]]) {
              temp[c[y]] = 1;
              y = fa[y];
            }
          } else
            y = p[y];
        }
      }

      if (keyid[x]) temp |= bs[keyid[key[bl[u]]]][keyid[x]];
      if (keyid[y]) temp |= bs[keyid[key[bl[v]]]][keyid[y]];

      while (x != y) {
        if (dep[x] > dep[y]) {
          temp[c[x]] = 1;
          x = fa[x];
        } else {
          temp[c[y]] = 1;
          y = fa[y];
        }
      }
      temp[c[x]] = true;
    }
    int ans1 = temp.count(), ans2 = find_first(~temp);
    cout << ans1 << ' ' << ans2 << '\n';
    lastans = (ans1 + ans2) * type;
  }

  return 0;
}

void dfs(int u) {  // Find points according to the problem statement
  int i, v, t = top;
  for (i = head[u]; i; i = nxt[i]) {
    v = to[i];
    if (v == fa[u]) continue;
    fa[v] = u;
    dep[v] = dep[u] + 1;
    dfs(v);
    if (top - t >= B) {
      key[++tot] = u;
      if (!keyid[u]) keyid[u] = tot;
      while (top > t) bl[sta[top--]] = tot;
    }
  }
  sta[++top] = u;
}

void add(int u, int v) {
  nxt[++cnt] = head[u];
  head[u] = cnt;
  to[cnt] = v;
}
```

BZOJ4812 Yuno Plays Poker

This problem is essentially the same as the previous one, with the only difference being how to compute the answer after obtaining the bitset.

Since BZOJ uses total time limit across all test cases, which is hard to fail, one can cheat by using _Find_next().

The correct solution is to compute every 16 bits together, first preprocessing the number of consecutive high bits, consecutive low bits, and the contribution in the middle for all \(2^{16}\) possible cases. However, this requires implementing a custom bitset, because the standard library's bitset cannot extract specific 16 bits...

Code can be found in this blog post.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用