Migrated from Lutece 3116 龙树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：dsu on tree

小$w$最近在玩怪猎。

有一天，小$w$发现了一棵有龙栖息的树。这棵树有$n$个节点，编号$1\sim n$，每个节点都有一条龙，第$i$个节点上的龙编号为$a_i$。

一条树上简单路径被称为$Drgon Road$，当且仅当：

1. 这条路径至少包含两个节点；
2. 这条路径的起点和终点上的龙编号相同；
3. 除了终点外，没有任何节点上的龙编号和起点上的龙编号相同。

现在小$w$想知道树上总共有多少条$Drgon Road$。

Input

第一行一个整数$T$，表示有$T$组测试数据。

接下来在每一组测试数据中：

第一行一个整数$n$，表示这颗树有$n$个节点。

第二行$n$个整数，第$i$个整数表示第$i$个节点上的龙的编号。

接下来$n-1$行，每行两个整数$x,y$，表示节点$x,y$间有一条无向边。

Output

对于每组测试数据，输出一行一个整数，表示$Drgon Road$的数量。

Samples

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

Constraints

$\sum n \leq 2\times 10^5 , 1\leq x,y,a_i \leq n$

Resources

2024 UESTC ICPC Training for Data Structure