[Contest][1]

[Practice][2]

**Author:** [Shivam Garg][3]

**Tester:** [Shiv Dhingra][4]

### DIFFICULTY

MEDIUM HARD

### PREREQUISITES

Mo’s on Trees

### PROBLEM

Given a tree, for each query comprising a path in the tree, it is required to answer **the minimum absolute difference between any two distinct nodes on that path.**

### EXPLANATION

In order to solve this problem, Mo’s algorithm on trees can be implemented.

In order to gain more insight into this algorithm, refer this [excellent source][5].

As explained in the above-mentioned post, we, first of all, need to **flatten the tree** and c**ompute the inTime[ ] and outTime [ ] via DFS.** Mo’s algorithm can be implemented over this contiguous interval.

Now, according to the algorithm, queries can be computed, as we **do not count the nodes which appear twice**.

Now, in order to compute the minimum absolute difference of squared value between any 2 distinct nodes, there are various ways.

One of them is via the **use of 2 multisets**. The **first** multiset stores **the squared values of the nodes.** The **second** multiset stores **the difference between closest/adjacent values in the first multiset**.

In case a new element is inserted into multiset 1, not more than **2 new differences** will be generated. These will be inserted in multiset 2. The same case holds when an element has to be deleted from multiset 1.

The **answer to each query** is the **first element of multiset 2**.

This question can also be solved by the use of **Segment Tree**. Whenever an element is to be **inserted or removed**, carry out the **update** operation in segment tree. Also, **at each node compute the minimum absolute difference of the squared value between its constituent leaf nodes.**

The complexity of multiset/segment tree is O(Log (N)), and that of Mo’s on Trees algorithm is O(Q \sqrt{N}). So, the overall complexity turns out to be O(Q \sqrt{N}Log (N)).

### SOLUTION

Setter’S Solution -

```
[6]
[1]: https://www.codechef.com/CODR2018/problems/KRYP2/
[2]: https://www.codechef.com/problems/KRYP2/
[3]: http://codechef.com/users/shivamg_isc
[4]: http://codechef.com/users/lucifer2709
[5]: http://codeforces.com/blog/entry/43230
[6]: https://www.codechef.com/viewsolution/17468445
```