Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Hasinur's Mission!

By Shahwat_Has9 · Limits 2s, 512 MB

Let me tell you something about Hasinur:

  1. He is a religious person. He prays 5 times a day.
  2. He loves math.
  3. He loves prime numbers.
  4. He loves to travel.

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.


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.

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.



97% Solution Ratio

peppermintEarliest, Apr '20

aritra741Fastest, 0.2s

fsshakkhorLightest, 13 MB

peppermintShortest, 1059B


Login to submit


This is a simple DP problem with a little of combinatorics in it. If you have the basic idea of dyna...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.