Welcome to ZOJ
 Problem Sets 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