14531453 SUSTech Online Judge
Problem 1453 --Paths

1453: Paths

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1417  Solved: 591
[Submit][Status][Web Board]


Given a rooted tree numbered from \(1\) to \(n\), each edge has a weight \(w\). The root node of the tree is node \(1\). You are asked to calculate the number of paths that start from the root, terminate in a leaf node, and satisfy the sum of edge weights in the path equals to \(num\).


The first line contains two integers \(n\) and \(num\)\((1 \leq n \leq 500\ 000, 1 \le num \le 2\ 000\ 000\ 000)\), indicating the number of tree nodes and the target number.

Then \(n-1\) lines follow. Each line contains three integers \(u,v,w\) \((1 \le u,v \le n, 1 \le w \le 100)\) describing an edge. The first two integers are the indices of nodes that form an edge and the last integer indicates the weight of the edge.


Output an integer which means how many paths satisfying the sum of edge weights in the path equals to \(num\).

Sample Input

6 6
1 2 2
1 3 3
3 4 4
3 5 3
2 6 4

Sample Output