1. Use the trick of Tree SQRT-Decomposition

I didn't find any Codeforces post describing this method, so I'm here to share this method. Also, I hope people could help me learn more about tree sqrt-decomposition.

Main Idea

The main idea of Mo's algorithm is to decompose sequence with size $$$N$$$ into $$$O(K)$$$ contiguous blocks, and if we re-order our queries $$$[L_i,R_i]$$$ with pair $$$(\text{BlockID}(L_i), R_i)$$$ and maintain two pointer of $$$L$$$ and $$$R$$$, we could get a $$$O(Q \frac{N}{K} + KN)$$$ complexity to solve some sequence problem.

It is because that every queries with the same $$$\text{BlockID}(L_i)$$$ shares the cost of moving the pointer of $$$R$$$ from leftmost to rightmost, so the pointer of $$$R$$$ will move at most $$$O(NK)$$$ elements. Also, the pointer of $$$L$$$ won't move more than $$$O(\frac{N}{K})$$$ elements when changing from one query range to another query range.

So, if we have a way to preserve these two properties ( i.e. we could share the cost of moving a pointer $$$R$$$ when those queries are in the same block, and we could correctly decompose our tree into some blocks such that moving a pointer $$$L$$$ between nodes in a single blocks won't cost to large ), we could apply a mo's algorithm on trees.

Tree SQRT-Decomposition

Here comes a way to decompose tree into blocks such that the size of blocks will be in the range $$$[K, 3K]$$$, and also the distance between nodes inside a single block won't exceed $$$O(3K)$$$.

The Algorithm

We could construct every blocks recursively.

Here is a pseudo implementation of this algorithm in C++.

int BlockID[N], BlockCount = 0;

// this function will return nodes that haven't been group into blocks
vector<int> DFS(int u) {
  vector<int> vertices_without_group;
  for (int v : child_of[u]) {
    // recursively process u's subtree
    auto sub = DFS(v);
    // merge nodes that haven't been group when proccesing u's subtree
    for (int s : sub) vertices_without_group.push_back(s);
    // when the size of block is big enough, we then make it a block
    if (vertex_without_group.size() >= K) {
      // mark those nodes
      for (int vertex_without_group : vertices_without_group)
        BlockID[vertex_without_group] = BlockCount;
      BlockCount++;
      vertices_without_group.clear();
    }
  }
  // u should be grouped by it's parent
  vertices_without_group.push_back(u);
  return vertices_without_group;
}
void group_tree_vertices(int root) {
  auto vertices_without_group = DFS(root);
  // notice that we may not need to add a new block for the rest nodes
  for (int vertex_without_group : vertices_without_group)
    BlockID[vertex_without_group] = BlockCount;
}

Analysis

So, why this algorithm work ( i.e. the size of blocks will be in the range $$$[K, 3K]$$$, and the distance between nodes inside a single block won't exceed $$$O(3K)$$$ )?

Obviously, we call vertices_without_group a block if and only if it's size is greater than $$$K$$$, so the size of a single block won't exceed $$$K$$$ and the size of the return value of DFS will be less than $$$K$$$. Also, when merging two sets with size both less than $$$K$$$, the resulting set will have a size less than $$$2K$$$. This proves the size of blocks constructed in DFS will be in the range $$$[K, 2K]$$$. However, the merging step in group_tree_vertices may make the size of the last block becomes greater than $$$2K$$$, but it won't make it over $$$3K$$$. Now, we proved that the size of every block will be in the range $$$[K, 3K]$$$.

Additionally, a single block is almost-connected ( i.e. if it is constructed when dfsing $$$u$$$, then after putting $$$u$$$ into that block, the block becomes a connected component ), so the distance between nodes inside a single block won't exceed its size. Thus, the distance won't exceed $$$O(3K)$$$.

Mo's Algorithm on Tree with Tree SQRT-Decomposition

So, how to apply mo's algorithm on trees to handle tree path problem?

We could find that if we maintain an edge set $$$T_u$$$ from root to $$$u$$$ and an edge set $$$T_v$$$ from root to $$$v$$$, then $$$T_u \operatorname{\triangle} T_v$$$ ( where $$$\operatorname{\triangle}$$$ means Symmetric difference ) will be the edge set between $$$u$$$ to $$$v$$$. Also, when we want to change our query from $$$(u, v)$$$ to $$$(p, q)$$$, we just need to transform $$$T_u$$$ to $$$T_u \operatorname{\triangle} ( T_u \operatorname{\triangle} T_p )$$$ and $$$T_v$$$ to $$$T_v \operatorname{\triangle} (T_v \operatorname{\triangle} T_q)$$$ ( because $$$(T_u \operatorname{\triangle} ( T_u \operatorname{\triangle} T_p )) \operatorname{\triangle} (T_v \operatorname{\triangle} (T_v \operatorname{\triangle} T_q)) = T_p \operatorname{\triangle} T_q $$$ ).

As implementing this algorithm, when we want to change our query from $$$(u,v)$$$ to $$$(p,q)$$$, we just need to traverse the path from $$$u$$$ to $$$p$$$ and $$$v$$$ to $$$q$$$, adding those edges into our set if they haven't been in our set, or remove them if they have been in our set.

bool inPath[N];
void SymmetricDifference(int u) {
  if (inPath[u]) {
    // remove this edge
  } else {
    // add this edge
  }
  inPath[u] ^= 1;
}
void traverse(int &origin_u, int u) {
  for (int g = lca(origin_u, u); origin_u != g; origin_u = parent_of[origin_u])
    SymmetricDifference(origin_u);
  for (int v = u; v != origin_u; v = parent_of[v])
    SymmetricDifference(v);
  origin_u = u;
}
struct Query {
  int u, v, id;
  // other information to record
} que[N];
void solve() {
  int U = 1, V = 1;
  for (int i = 0; i < q; ++i) {
    traverse(U, que[i].u);
    traverse(V, que[i].v);
    // now we get the answer between que[i].u and que[i].v
  }
}

But how to re-order our query?

We could sort our queries $$$(u_i, v_i)$$$ with $$$(\text{BlockID}(u_i), \text{dfn}(v_i))$$$ ( where $$$\text{dfn}(u)$$$ means the time we enter our tree in a dfs procedure ).

This preserves the properties described above because moving a pointer between a single block cost $$$O(K)$$$ and traverse the tree with $$$\text{dfn}$$$ equals to traversing the tree with dfs, and thus, it cost $$$O(N)$$$.

As a result of this algorithm, we could first sqrt-decompose our tree and sort our queries base on it, and apply a mo's algorithm on it.

// save the tree using adjacency list
nxt[(i << 1) | 0] = hd[u];
to[(i << 1) | 0] = v;
hd[u] = (i << 1) | 0;

nxt[i << 1 | 1] = hd[v];
to[(i << 1) | 1] = u;
hd[v] = (i << 1) | 1;

2. Use The Property of Euler Tour

It has been described in Mo's Algorithm on Trees [Tutorial], so I'm not going to introduce this method thoroughly in this post.

Main Idea

This method use the property of euler tour, so we could construct a sequence and do a modified mo's algorithm on that sequence.