Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4080
Sortable Path on Tree

Time Limit: 1 Second      Memory Limit: 65536 KB

Chiaki has a tree with $n$ nodes numbered $1$ to $n$. Each nodes has a positive integer weight $w_i$ on it.

Chiaki would like to know the number of unordered pairs $(u,v)$ such that:

Let $t_1 \to t_2 \to \dots \to t_k$ ($t_1=u,t_k=v$) be the shortest path from $u$ to $v$. Then the sequence $w_{t_1}, w_{t_2}, \dots, w_{t_k}$ or the sequence $w_{t_k}, w_{t_{k-1}}, \dots, w_{t_1}$ can be sorted into nondecreasing order using several circular shift operations.

Note that a circular shift is the operation of rearranging the entries in a sequence, either by moving the final entry to the first position, while shifting all other entries to the next position, or by performing the inverse operation.

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 10^5$) -- the number of nodes in the tree.

The second line contains $n$ integers $w_1,w_2,\dots,w_n$ ($1 \le w_i \le 10^5$).

Each of the next $n-1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n, u \ne v$) denoting an edge on tree.

It's guaranteed that the sum of $n$ in all test cases will not exceed $10^5$.

Output

For each test case, output an integer denoting the answer.

Sample Input

1
4
3 4 1 2
1 2
2 3
3 4

Sample Output

10

Author: LIN, Xi
Source: Yet Another Xi Lin Contest
Submit    Status