
ZOJ Problem Set  4080
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_{k1}}, \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. InputThere 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 $n1$ 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$. OutputFor each test case, output an integer denoting the answer. Sample Input1 4 3 4 1 2 1 2 2 3 3 4 Sample Output10 Author: LIN, Xi Source: Yet Another Xi Lin Contest 