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]

## Description

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$$.

## Input

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

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

2

[Submit][Status]