Tasks:
 
Task DescriptionDiscussion (0)
Task :: 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

INPUT:
The 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.

OUTPUT:
To 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:
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 2

Output:
9


Explanation:
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:
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 3

Output:
3


Explanation:
Resulting simple chains are:
4 - 5; 6 - 7 - 8 - 9; 8 - 9 - 10.
Submit Solution
:
:
Available Languages
Task info
Name:z-sumpaths
Time:0.5 sec.
Memory:64 MB
#Tests:25
AddedBy: admin
Source:Slobodan Mitrović
Task Ratings
Difficulty:

3.3 (16 votes)
Quality:

3.6 (14 votes)
Acceptance Rate
Recent Submissions
Fastest Solutions
UserTime
evanlimanto 0.434 s.
_qwAker_ 0.487 s.
vjudge1 0.506 s.
vjudge5 0.529 s.
minchurl 0.535 s.
plt2312 0.569 s.
vjudge3 0.569 s.
crusader 0.573 s.
vjudge4 0.573 s.
vjudge2 0.574 s.
Solved By