z-sumpaths
You are given an undirected weighted tree with N nodes. You should count the number of simple chains in the tree such that the sum of edges of particular simple chain is exactly M. Output the result with modulo 321555123
InputThe first line of the standard input contains two space-separated integers N (2 <= N <= 50 000) and M (1 <= M <= 100). Each of the next N - 1 lines will contain three space-separated integers a, b (1 <= a, b <= N) and w (1 <= w <= 100), meaning that there is an edge {a, b} with the cost w.
OutputTo the first line of the standard output you should print the count of the simple chains with the described property. The result should be printed with modulo 321555123.
Input:
Output:
9 4
2 1 2
1 3 2
1 5 2
5 7 2
2 4 2
4 8 2
4 9 2
7 6 2Output:
9Explanation:
Each simple chain of length 2 is the solution:
1 - 2 - 4; 2 - 4 - 8; 2 - 4 - 9; 8 - 4 - 9; 2 - 1 - 3; 5 - 1 - 2; 3 - 1 - 5; 1 - 5 - 7; 5 - 7 - 6.
Input:
Output:
10 7
1 2 3
2 3 1
3 4 9
4 5 7
5 6 2
6 7 1
7 8 2
8 9 4
9 10 3Output:
3Explanation:
Resulting simple chains are:
4 - 5; 6 - 7 - 8 - 9; 8 - 9 - 10.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.