Product on Tree

All submissions for this problem are available.
Read problems statements in Mandarin Chinese , Russian and Vietnamese
Chef is going to leave his home town and shift to a new city. The new city contains exactly N houses. There are roads connecting the houses in such a way that there is exactly one way to go from a house to any other house. Length of each of the roads is known to Chef.
Chief is doing a lot of research before shifting to the new city. He wants to know how many pairs of houses (a,b) are there, such that if we multiply length of all the roads on the path from a to b, the product will be divisible by M.
Input
 First line of the input contains a pair of integers N and M, where N denotes the number of houses.
 Each of the next (N1) lines contains a triplet of numbers (a,b,c) which will denote that the length of the road between houses a and b is c.
Output
A single integer denoting the number of pair of houses.Constraints
 1 ≤ M ≤ 500
 1 ≤ weight of the road ≤ 10^{9}
Subtask #1: 20 points
 1 ≤ N ≤ 10^{5}
 M is a prime
 1 ≤ N ≤ 1000
 1 ≤ N ≤ 10^{5}
Example
Input: 4 2 1 3 4 1 2 4 1 4 4 Output: 6
Explanation
If we multiply the lengths of the roads on the path between any pair of the vertices, it will be divisible by 2.Author:  amitpandeykgp 
Tester:  pushkarmishra 
Editorial  http://discuss.codechef.com/problems/TREEPROD 
Tags  amitpandeykgp, dfs, dynamicprogramming, ltime30, tree 
Date Added:  13112015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 