Tree Inversions

★★★★★

5 votes

Square Root Decomposition, Algorithms, Advanced Algorithms

Details

Problem

You are given a tree with $N$ nodes and $N-1$ edges. Each node $i$ of the tree is assigned a color $A[i]$ . Let $c(x, y)$ be the array of colors encountered while traversing from node $x$ to node $y$ in the tree in the order.

Let $f(x, y)$ represent the number of inversions in the array $c(x, y)$ .

You need to compute $f(x, y) + f(y, x)$ for $Q$ different queries.

Inversions in an array $arr$ is equal to the count of pairs $(i, j)$ such that $i < j$ and $arr[i] > arr[j]$ .
A tree is a graph with $N$ nodes and $N-1$ edges such that it is possible to travel from any node to any other node.

Input format

First line of the input contains an integer $T$ , representing the number of test cases.
The first line of each test case contains $2$ space-separated integers $N$ , $Q$ representing the number of nodes and the number of queries respectively.
The next line of each test case contains $N$ integers seperated by a space representing array $A$ , the array of colours.
Next $N-1$ lines of each test case contains $2$ integers space-separated integers $X, Y$ each $(X, Y)$ , representing that there's an edge between node $X$ to node $Y$ .
The next $Q$ lines of each test case contains $2$ space-separated integers $x, y$ each $(x, y)$ representing the queries.

Output format

For each query output the answer in a new line representing the value $f(x, y) + f(y, x)$ .

Constraints

$1 \leq T \leq 10^5$
$2 \leq N, Q \leq 10^5$
$1 \leq A[i] \leq N$
$1 \leq X, Y \leq N, X \neq Y$
$1 \leq x, y \leq N, x \neq y$
It is guranteed that sum of $N$ , $Q$ over all test cases does not exceed $10^5$

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

In the first query $(4, 6)$ -
- the path from 4 to 6 contains nodes $4 \rightarrow 2 \rightarrow 1 \rightarrow 3 \rightarrow 6$ so $c(x, y)$ is $[1, 2, 1, 3, 1]$ . Here $f(x, y)$ = 3
- the path from 6 to 4 contains nodes $6 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4$ so $c(y, x)$ is $[1, 3, 1, 2, 1]$ . Here $f(y, x)$ = 4
- Clearly $f(x, y) + f(y, x)$ = 7
In the second query $(7, 8)$ -
- the path from 7 to 8 contains nodes $7 \rightarrow 5 \rightarrow 3 \rightarrow 6 \rightarrow 8$ so $c(x, y)$ is $[3, 2, 3, 1, 1]$ . Here $f(x, y)$ = 7
- the path from 8 to 7 contains nodes $8 \rightarrow 6 \rightarrow 3 \rightarrow 5 \rightarrow 7$ so $c(y, x)$ is $[1, 1, 3, 2, 3]$ . Here $f(y, x)$ = 1
- Clearly $f(x, y) + f(y, x)$ = 8