405241: GYM101856 E Evaluations

For World Cup marketing purposes, FIFA wants to evaluate the compatibility of different players. Some players have connections that affect their compatibility scores, like being from the same country or playing in the same team. These connections are well studied, and for some pairs of players, an integer value is assigned based on these connections. After such studies, FIFA found out that the set of players with connections form an undirected tree. In more details, players are the nodes of the tree and edges connect players with a connection such that the edge’s weight is equal to the value of this connection. It is guaranteed that these edges will form a tree. The compatibility score of players u, v is:

• If there is an edge (u, v) in the tree, then it is the weight of that edge.
• Otherwise, it is the weight of the path between u and v, such that the weight of a path is the product of the weights of its edges.

Given the tree of players along with edges’ weights, FIFA is interested in counting the number of distinct unordered pairs of players u, v such that their compatibility score is a product of exactly two distinct primes.

The first line of the input contains a single integer 1 ≤ T ≤ 100 the number of test cases. Each test case consists of n lines, the first line containing a single integer n. Each of the remaining n - 1 lines consists of 3 space separated integers ; each of those denotes an edge between the nodes x and y with weight w; where 1 ≤ x, y ≤ n ≤ 10⁵ and 1 ≤ w ≤ 10⁵.

For each test case output a single line displaying the case number and the count.

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

Case 1: 3

An unordered pair is a set of two distinct elements. {a, b} = {b, a}.