Let me tell you something about Hasinur:
Hasinur travels a lot. When he visits a city, he goes through every mosque of that particular city and prays.
In January 2020, he had a chance to visit a city in India called Sikkim. After reaching Sikkim, his first target was to visit all the mosques situated in Sikkim. Hasinur collected a map where he found the location of all the mosques located at Sikkim and the roads that connect them. It is guaranteed that he can go to any mosque from any other mosque using only one single path. A path consists of one or more roads.
There are n mosques in the city of Sikkim. All the mosques are connected by a total of (n - 1) roads. The roads are bi-directional and have a number associated with it. Hasinur knows the location of all the mosque, he knows the number of all the roads and the path between every mosque in that city.
Hasinur likes prime numbers as well. So he wants to know how many combinations of (X, Y, Z) of mosques are there where he would be able to visit at least one road associated with a prime number along the way while going from X to Y and also from X to Z. Here, mosque X ≠ mosque Y ≠ mosque Z.
The first line will contain n (2 ≤ n ≤106), the number of mosques in Sikkim.
Next (n - 1) lines each will contain 3 numbers: a, b, and c (1 ≤ a, b ≤ n; a ≠ b; 1 ≤ c ≤ 106), denoting there is a road between a and b, and c is the number associated with that particular road.
Output a single integer denoting the answer.
7 1 2 1 2 7 7 2 5 12 1 4 15 1 3 7 3 6 10
The first few of possible combinations are (1,7,3) , (1,3,7), (1,7,6), (2,3,7) and so on.
Figure: The map of city 'Sikkim' according to the sample input.
The green marked roads are the road associated wiht a prime number.
4 1 3 2 1 2 5 1 4 20
The possible combinations are: (3,4,2), (2,3,1), (3,1,4) (1, 2, 3), (4,3,2), (2,4,1), (3,2,1), (3,4,1) (2,1,3), (1,3,2), (2,1,4), (4,2,3), (2,3,4), (2,4,3), (3,1,2), (3,2,4).
Figure: The map according to the sample input/output.
Dataset is huge. Use faster I/O methods.
Login to submit
This is a simple DP problem with a little of combinatorics in it. If you have the basic idea of dyna...