Given a tree consisting of M vertices and N-1 weighted edges. The edges are numbered from 1 to N-1; the i-th edge connects the pair of vertices (u, v) and has weight c.

The path cost between two vertices (u, v) is the sum of the weights of the edges on the path from u to v (u ≠ v). If there is no path from u to v, the path cost for the pair (u, v) is 0.

An edge deletion method is described as follows:

Choose two positive integers L, R satisfying 1 ≤ L ≤ R ≤ N — 1;

Delete all edges numbered from L to R;

Given a positive integer K. An edge deletion method is called "beautiful" if every path cost between any pair of vertices does not exceed K. Two edge deletion methods are considered different if there is an edge present in one method but not in the other.

Requirement: Count the number of "beautiful" edge deletion methods. Constraints: N <= 1e5 Time limit: 1-2s

Sample input: 6 12

1 2 3

1 4 5

2 3 6

2 5 4

3 6 9

The answer is 9.

Please help me with this problem. Thank you very much. Here is the code for my smaller subtasks. Link: https://ide.usaco.guide/OaV3EO7Zu9DRl2APo19