Tree Inversions

4

5 votes
Square Root Decomposition, Algorithms, Advanced Algorithms
Problem

You are given a tree with N nodes and N1 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 N1 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 NQ 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 N1 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

  • 1T105
  • 2N,Q105
  • 1A[i]N
  • 1X,YN,XY
  • 1x,yN,xy
  • It is guranteed that sum of N, Q over all test cases does not exceed 105

 

Sample Input
1
8 7
1 2 3 1 2 1 3 1
1 2
1 3
2 4
3 5
3 6
5 7
6 8
4 6
7 8
5 4
7 6
3 8
1 2
4 8
Sample Output
7
8
8
5
2
1
9
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

  • In the first query (4,6) - 
    • the path from 4 to 6 contains nodes 42136 so c(x,y) is [1,2,1,3,1]. Here f(x,y) = 3
    • the path from 6 to 4 contains nodes 63124 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 75368 so c(x,y) is [3,2,3,1,1]. Here f(x,y) = 7
    • the path from 8 to 7 contains nodes 86357 so c(y,x) is [1,1,3,2,3]. Here f(y,x) = 1
    • Clearly f(x,y)+f(y,x) = 8
Editor Image

?