牧场建设（Constructing Ranches）

牧场和牛仔传统起源于西班牙，源于在马背上管理干旱土地上大群放牧牲畜的需要。在收复失地运动期间，西班牙贵族和各个军事教团获得了卡斯蒂利亚王国从摩尔人手中征服的大片土地。这些土地所有者负责保卫他们控制下的土地，并可以利用这些土地赚取收入。在此过程中，人们发现开放式放牧牛羊（在 Mesta 系统下）是利用大片土地最合适的方式，特别是在现在被称为卡斯蒂利亚-拉曼恰、埃斯特雷马杜拉和安达卢西亚的西班牙地区。

美国俄克拉荷马州历史悠久的 101 牧场。公共领域。

Jace 是国际牛业生产公司（ICPC）的一名员工，他今天的任务是帮助他的客户 Karn 建造一个新的牛牧场。Jace 和 Karn 都同意牧场应该用栅栏围起来以确保安全，并且牧场的形状应该是一个简单多边形。回想一下，简单多边形是指不自交且没有孔的多边形。也就是说，它是一个由直线、不相交的线段连接而成的封闭路径的平面形状。简单多边形总是具有可测量的且严格为正的面积。

Karn 居住的城镇里有 $n$ 家商店出售栅栏段，为了方便起见，它们被编号为 $1$ 到 $n$。恰好有 $n-1$ 条双向道路连接这些商店，并且使用这些道路在任意两家商店之间旅行都只有唯一的一条简单路径。换句话说，商店和道路在图论中构成了一棵树。第 $i$ 家商店只出售一段栅栏，其长度为 $a_i$。Jace 计划从一家商店 $x$ 旅行到另一家商店 $y$，并购买从 $x$ 到 $y$ 的唯一简单路径上所有商店的栅栏段（包括 $x$ 和 $y$）。然后，他将尝试用他购买的栅栏段建造栅栏（如上所述，它必须是一个简单多边形）。由于 Karn 不想浪费任何钱，Jace 必须在栅栏中使用所有购买的栅栏段。请帮助 Jace 计算有多少对 $(x, y)$ 满足 $x < y$，且 Jace 在从 $x$ 旅行到 $y$ 时可以建造一个有效的栅栏。

输入格式

输入包含多个测试用例。输入的第一行包含一个正整数 $T$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)，表示商店的数量。 第二行包含 $n$ 个整数，其中第 $i$ 个 ($1 \le i \le n$) 整数 $a_i$ ($1 \le a_i \le 10^9$) 表示第 $i$ 家商店出售的栅栏段的长度。接下来的 $n-1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示商店 $u$ 和商店 $v$ 之间的一条双向道路。保证商店和道路构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $4 \cdot 10^5$。

输出格式

对于每个测试用例，在一行中输出一个整数，表示有效的对 $(x, y)$ 的数量。

样例

输入 1

2
3
1 10 100
1 2
3 2
5
1 1 1 1 1
1 2
1 3
1 4
1 5

输出 1

0
6

说明 1

在第二个样例中，以下对是有效的：$(2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)$。