AIOJ

Ways to Decompose a Tree

You can also see ouuan's blog / Detailed explanation of Mo's algorithm, Mo's algorithm with modifications, and Mo's algorithm on trees / Mo's algorithm on trees.

The two articles above also cover Mo's algorithm on trees.

Applications of Tree Decomposition

Besides being used with Mo's algorithm, tree decomposition can be applied flexibly to some problems on trees. However, problems that can be solved with tree decomposition often have better approaches, so there are relatively few such problems.

As an aside, the tree-decomposition solution for “gty's Girl Tree” can be defeated by a star graph.

BZOJ4763 Xuehui

First decompose the tree into blocks. For each key point in every block, precompute a bitset of the colors on the path from it to each key-point ancestor, as well as its nearest key-point ancestor. The complexity is $O(n\sqrt n+\frac{nc}{32})$ : $n\sqrt n$ is the complexity of naively jumping upward from every key point, and $\frac{nc}{32}$ is the complexity of storing $O(n)$ bitsets.

When answering a query, first jump naively from the endpoints of the path to the key points of their blocks. Then jump upward block by block from the key points of the current blocks until reaching the block containing the $lca$ , and finally jump naively to the $lca$ . The bitsets between key points have already been precomputed; the remaining information is computed during the naive jumps. The complexity of one query is $O(\sqrt n+\frac c{32})$ : $\sqrt n$ is the complexity of naive jumps inside a block and direct upward jumps between blocks, while $O(\frac c{32})$ is the complexity of merging the precomputed result with the result of the naive jumps. The number of colors can be counted with bitset's count(), and $\operatorname{mex}$ can be found with bitset's _Find_first().

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

Reference code

#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) {  // on the first jump, walk directly to the key point
            while (x != key[bl[u]]) {
              temp[c[x]] = 1;
              x = fa[x];
            }
          } else
            x = p[x];  // otherwise jump an entire 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 Younoi Plays Poker

This problem is basically the same as the previous one; the only difference is how to compute the answer after obtaining the bitset.

~~Since BZOJ measures the total time limit over all test points and is difficult to hack, one can get by with _Find_next().~~

The intended solution is to process $16$ bits at a time. First precompute, for all $2^{16}$ possible cases, the number of consecutive $1$ bits at the high end, the number of consecutive $1$ bits at the low end, and the contribution in the middle. However, this requires implementing bitset by hand, because the standard-library bitset cannot extract an arbitrary $16$ -bit segment.

See this blog post for reference code.