406595: GYM102452 C Constructing Ranches

Ranching and the cowboy tradition originated in Spain, out of the necessity to handle large herds of grazing animals on dry land from horseback. During the Reconquista, members of the Spanish nobility and various military orders received large land grants that the Kingdom of Castile had conquered from the Moors. These landowners were to defend the lands put into their control and could use them for earning revenue. In the process, it was found that open-range breeding of sheep and cattle (under the Mesta system) was the most suitable use for vast tracts, particularly in the parts of Spain now known as Castilla-La Mancha, Extremadura and Andalusia.

The historic 101 Ranch in Oklahoma, US. Public domain.

Jace is an employee at the International Cattle Production Company (ICPC), whose mission today is to help his client Karn to build a new cattle ranch. Both Jace and Karn agree that the ranch should be surrounded by fences to ensure security, and the shape of the ranch should be a simple polygon. Recall that a simple polygon is a polygon that does not intersect itself and has no holes. That is, it is a flat shape consisting of straight, non-intersecting line segments that are joined to form a single closed path. A simple polygon always has a measurable and strictly positive area.

There are $$$n$$$ shops selling fence segments in the town where Karn lives, they are numbered from $$$1$$$ to $$$n$$$ for convenience. Exactly $$$n-1$$$ bidirectional roads are connecting the shops, and there is exactly one simple path to travel between any two shops using those roads. In other words, the shops and roads form a tree in graph theory. The $$$i$$$-th shop only has a single fence segment for sale, whose length is $$$a_i$$$. Jace plans to travel from one shop $$$x$$$ to another shop $$$y$$$, and buy all fence segments from the shops on the only simple path from $$$x$$$ to $$$y$$$ (including $$$x$$$ and $$$y$$$). Then, he will try to build the fence (as mentioned above, it must be a simple polygon) with the segments he has bought. Since Karn doesn't want to waste any money, Jace must use all the segments in the fence. Please help Jace calculate how many pairs $$$(x,y)$$$ are there such that $$$x<y$$$, and Jace can build a valid fence if he travels from $$$x$$$ to $$$y$$$.

The input contains multiple cases. The first line of the input contains a single positive integer $$$T$$$, the number of cases.

For each case, the first line of the input contains a single integer $$$n \ (1 \le n \le 2\cdot 10^5)$$$, the number of shops. The second line contains $$$n$$$ integers, where the $$$i$$$-th ($$$1 \le i \le n$$$) integer $$$a_i\ (1 \le a_i \le 10^9)$$$ denotes the length of the fence segment on sale at the $$$i$$$-th shop. The following $$$n-1$$$ lines each contains two integers $$$u,v \ (1\le u,v \le n)$$$, denoting a bidirectional road between shop $$$u$$$ and shop $$$v$$$. It is guaranteed that the shops and roads form a tree.

It is guaranteed that the sum of $$$n$$$ over all cases doesn't exceed $$$4\cdot 10^5$$$.

For each case, print a single integer in a single line, the number of valid pairs $$$(x,y)$$$.

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

0
6

In the second sample case, the following pairs are valid: $$$(2,3),\ (2,4),\ (2,5),\ (3,4),\ (3,5),\ (4,5)$$$.