There is no partial marking in the problem.
Given a weighted undirected tree of N nodes and Q queries. Each query contains an integer D. For each query, find the number of paths in the given tree such that all the edges in the path are divisible by D.
Input Format:
First line contains two space separated integers, N and Q \((1 \le N, Q \le 10^5)\), denoting number of nodes in the tree and number of queries. Next \(N-1\) line contains three space separated integers, X, Y and W \((1 \le X, Y \le N)\) \((1 \le W \le 10^5)\), denoting that there is an edge between X and Y of weight W. Next Q lines contains one integer each, D \((1 \le D \le 10^5)\).
Output Format:
For each query, print number of paths such that all the edges in the path are divisible by D in new line.
5 2 1 2 10 1 3 6 3 4 15 3 5 15 5 3
4 6
First query, \(D = 5\) :
There are 4 paths such that all the edges in the path are divisible by D.
1. 1 -> 2
2. 3 -> 4
3. 3 -> 5
4. 4 -> 3 -> 5
Second query, \(D = 3\) :
There are 6 paths such that all the edges in the path are divisible by D.
1. 1 -> 3
2. 3 -> 4
3. 3 -> 5
4. 4 -> 3 -> 5
5. 1 -> 3 -> 5
6. 1 -> 3 -> 4
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor