CF1923E Count Paths

给定一棵包含 $n$ 个顶点的树，顶点编号为 $1$ 到 $n$。每个顶点被染成某种颜色，颜色用 $1$ 到 $n$ 之间的整数表示。 一条树上的简单路径被称为“美丽路径”，当且仅当： - 路径包含至少 $2$ 个顶点； - 路径的起点和终点颜色相同； - 路径上的其他顶点都不与起点颜色相同。 请计算树中美丽简单路径的数量。注意，路径是无向的（即从 $x$ 到 $y$ 的路径与从 $y$ 到 $x$ 的路径视为同一条路径）。

第一行包含一个整数 $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$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \le v_i, u_i \le n$，$v_i \neq u_i$），表示树中的一条边。 给定的边构成一棵合法的树。所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示美丽简单路径的数量。

由 ChatGPT 4.1 翻译