Sortable Path on Tree

题号：NC21533
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

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₁=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.

输入描述:

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 ≤ n ≤ 10⁵) -- the number of nodes in the tree.
The second line contains n integers w₁,w₂,...,w_n (1 ≤ w_i ≤ 10⁵).
Each of the next n-1 lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) denoting an edge on tree.
It's guaranteed that the sum of n in all test cases will not exceed 10⁵.

输出描述:

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

示例1

输入

复制

输出

复制