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.
A simple implementation in C++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.
A template of Mo's algorithm on tree in C++```cpp int n, q; int nxt[N], to[N], hd[N];
struct Que { int u, v, id; } que[N];
void init() { // read how many nodes and how many queries cin >> n >> q; // read the edge of tree for (int i = 1; i < n; ++i) { int u, v; cin >> u >> v;
// 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;
}
for (int i = 0; i < q; ++i) { // read queries cin >> que[i].u >> que[i].v; que[i].id = i; } }
int dfn[N], dfn_, block_id[N], block_;
int stk[N], stk_;
void dfs(int u, int f) { dfn[u] = dfn_++;
int saved_rbp = stk_;
for (int v_ = hd[u]; v_; v_ = nxt[v_]) { if (to[v_] == f) continue; dfs(to[v_], u); if (stk_ — saved_rbp < SQRT_N) continue; for (++block_; stk_ != saved_rbp;) block_id[stk[--stk_]] = block_; }
stk[stk_++] = u; }
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; }
void solve() { // construct blocks using dfs dfs(1, 1); while (stk_) block_id[stk[--stk_]] = block_; // re-order our queries sort(que, que + q, [](const Que &x, const Que &y) { return tie(block_id[x.u], dfn[x.v]) < tie(block_id[y.u], dfn[y.v]); }); // apply mo's algorithm on tree int U = 1, V = 1; for (int i = 0; i < q; ++i) { pass(U, que[i].u); pass(V, que[i].v); // we could our answer of que[ i ].id } }```
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.