401907: GYM100570 F Tree Query

De Prezer loves trees. A tree of order n is a connected graph with n vertexes and n - 1 edges.

De Prezer also loves query.

De Prezer has a weighted tree of order n (each edge has a length). The distance between two vertexes is the sum of length of edges between them and we show it by d(v, u) (distance between vertexes u and v).

De Prezer ask you to perform q queries on this tree.

Each query gives you numbers v, l and you should tell him the number of vertexes like u such that d(v, u) ≤ l (including v itself).

The first line of input contains integers n and q .

The next n - 1 lines contain edges. Each line contains an edge a, b, w, two endpoints and the weight.

The next q lines, contain queries.

1 ≤ n, q ≤ 10⁵

1 ≤ v ≤ n

1 ≤ l ≤ 10¹⁴

1 ≤ a, b ≤ n

1 ≤ w ≤ 10⁹

For each query, print a single integer in a single line.

4 6
1 2 3
2 3 10
3 4 51
1 2
1 10
3 30
3 51
2 60
2 61

1
2
3
4
3
4

5 5
1 2 100
1 3 100
1 4 10
1 5 200
1 99
1 199
1 299
4 100
4 110

2
4
5
2
4