311029: CF1923E. Count Paths

E. Count Pathstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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$).

Input

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$.

Output

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

ExampleInput

4
3
1 2 1
1 2
2 3
5
2 1 2 1 2
1 2
1 3
3 4
4 5
5
1 2 3 4 5
1 2
1 3
3 4
4 5
4
2 2 2 2
3 1
3 2
3 4

Output

1
3
0
3

题目大意：计算一棵树的“美丽”简单路径的数量。一棵树由n个顶点组成，顶点编号从1到n，每个顶点都有一种颜色，用1到n的整数表示。如果一条路径至少包含2个顶点，路径的第一个和最后一个顶点颜色相同，且路径上除首尾顶点外的其它顶点颜色都与首顶点不同，则称这条路径为“美丽”的。路径被认为是无向的（即从x到y的路径与从y到x的路径相同）。输入包括多个测试案例，每个测试案例包括顶点数n、每个顶点的颜色以及n-1条边的顶点对。输出每个测试案例的“美丽”简单路径数量。

输入输出数据格式：
- 输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试案例的数量。
- 每个测试案例的第一行包含一个整数n（2≤n≤2×10^5），表示顶点的数量。
- 第二行包含n个整数c_1, c_2, ..., c_n（1≤c_i≤n），表示每个顶点的颜色。
- 接下来的n-1行，每行包含两个整数v_i和u_i（1≤v_i, u_i≤n；v_i≠u_i），表示树的一条边。
- 输出：
- 对于每个测试案例，输出一个整数，表示该树中“美丽”简单路径的数量。

示例输入：
```
4
3
1 2 1
1 2
2 3
5
2 1 2 1 2
1 2
1 3
3 4
4 5
5
1 2 3 4 5
1 2
1 3
3 4
4 5
4
2 2 2 2
3 1
3 2
3 4
```

示例输出：
```
1
3
0
3
```题目大意：计算一棵树的“美丽”简单路径的数量。一棵树由n个顶点组成，顶点编号从1到n，每个顶点都有一种颜色，用1到n的整数表示。如果一条路径至少包含2个顶点，路径的第一个和最后一个顶点颜色相同，且路径上除首尾顶点外的其它顶点颜色都与首顶点不同，则称这条路径为“美丽”的。路径被认为是无向的（即从x到y的路径与从y到x的路径相同）。输入包括多个测试案例，每个测试案例包括顶点数n、每个顶点的颜色以及n-1条边的顶点对。输出每个测试案例的“美丽”简单路径数量。 输入输出数据格式： - 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试案例的数量。 - 每个测试案例的第一行包含一个整数n（2≤n≤2×10^5），表示顶点的数量。 - 第二行包含n个整数c_1, c_2, ..., c_n（1≤c_i≤n），表示每个顶点的颜色。 - 接下来的n-1行，每行包含两个整数v_i和u_i（1≤v_i, u_i≤n；v_i≠u_i），表示树的一条边。 - 输出： - 对于每个测试案例，输出一个整数，表示该树中“美丽”简单路径的数量。 示例输入： ``` 4 3 1 2 1 1 2 2 3 5 2 1 2 1 2 1 2 1 3 3 4 4 5 5 1 2 3 4 5 1 2 1 3 3 4 4 5 4 2 2 2 2 3 1 3 2 3 4 ``` 示例输出： ``` 1 3 0 3 ```