MO's ( Query-Sqrt Decomposition) Algorithm on Tree

I was trying hard to solve a problem from July Long Challenge and even after one day of thinking i was not able to solve it. So i decided to solve sub-tasks. For solving sub-tasks, i decided to use MO's algo (aka Query-Sqrt Decomposition).

Prerequisite: MO's algorithm, Euler tour technique (ETT).

So, I needed to do queries on edges (weights) of undirected tree. After searching little bit, i found this article on codeforces. It's a good article. I learnt how to do queries on path for a given tree but the problem was to do queries on edges, not vertices.

After thinking for a while, i came up with a solution. I stored the ETT of the tree in a vector and did all the queries on the ETT. In this method we don't need to find LCA. All we need to do is store the position of first occurrence of each element in an array. For doing query between u and v, we need to do query between firstOccurrence(u) to firstOccurrence(v). While doing query, if an edge occurs twice, we need to remove its contribution from answer. It will be more clear from the following example:

Let us find the sum between u and v for the given tree.

 The ETT for the above example is : { 1, 2, 3, 4, 3, 2, 5, 6, 5, 2, 1, 7, 8, 7, 9, 7, 1}
(How?  open this).

Code for finding ETT:


Now for example i want to do query between 6 to 9.

(Assuming 0-based index)

L = firstOccurrence(6)
R = firstOccurrence(9)

so L = 7  and R = 14

{ 1, 2, 3, 4, 3, 2, 5, 6, 5, 2, 1, 7, 8, 7, 9, 7, 1,}

The answer is (6 -> 5) + (5 -> 2)+ (2 -> 1) + (1 -> 7) + (7 -> 8) -  (8 -> 7) + (7 -> 9), i.e., 8+2+5+4+1-1+6 = 25.
As i mentioned earlier, if an edge comes twice we will delete its contribution to answer, that is why we removed (8->7)'s weight, as it has occurred earlier.

I hope, you guys find it helpful and interesting!