CF1923E.Count Paths

You are given a tree, consisting of $n$ vertices, numbered from $1$ to $n$. Every vertex is colored in some color, denoted by an integer from $1$ to $n$.

A simple path of the tree is called beautiful if:

• it consists of at least $2$ vertices;
• the first and the last vertices of the path have the same color;
• no other vertex on the path has the same color as the first vertex.

Count the number of the beautiful simple paths of the tree. Note that paths are considered undirected (i. e. the path from $x$ to $y$ is the same as the path from $y$ to $x$).

给你一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。每个顶点均被染成某种颜色，颜色用 $1$ 到 $n$ 之间的整数表示。

树中的一条简单路径被称为优美的，当且仅当满足以下条件：

• 该路径至少包含 $2$ 个顶点；
• 路径的起点与终点顶点颜色相同；
• 路径上除起点与终点外的其余所有顶点，其颜色均不同于起点（即终点）的颜色。

请计算该树中优美简单路径的数量。注意：路径是无向的（即从 $x$ 到 $y$ 的路径与从 $y$ 到 $x$ 的路径视为同一条路径）。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of vertices in the tree.

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$) — the color of each vertex.

The $i$-th of the next $n - 1$ lines contains two integers $v_i$ and $u_i$ ($1 \le v_i, u_i \le n$; $v_i \neq u_i$) — the $i$-th edge of the tree.

The given edges form a valid tree. The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 树中顶点的数量。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le n$）—— 每个顶点的颜色。

接下来的 $n - 1$ 行中，第 $i$ 行包含两个整数 $v_i$ 和 $u_i$（$1 \le v_i, u_i \le n$；$v_i \neq u_i$）—— 树的第 $i$ 条边。

所给的边构成一棵合法的树。所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each testcase, print a single integer — the number of the beautiful simple paths of the tree.

对于每个测试用例，输出一个整数——树中优美简单路径的数量。