### oToToT's blog

By oToToT, 9 months ago, , # 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++

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++

# 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. 