Distinct LCA Depth Sums in a Tree

Given a tree with (n) nodes and the root at node (1), where each edge has a weight, you are to answer (m) queries. Define the depth of a node (x), (dep(x)), as the sum of the edge weights on the simple path from the root to (x). Let (lca(x,y)) denote the lowest common ancestor of nodes (x) and (y) in the tree.

For each query, you are given two integers (l) and (r). Consider all pairs of nodes ((i, j)) with (l \le i, j \le r) (note that pairs where (i = j) are allowed). Your task is to compute the number of distinct values of (dep(lca(i,j))) over all these pairs.

inputFormat

The first line contains two integers (n) and (m), representing the number of nodes and the number of queries respectively.

The next (n-1) lines each contain three integers (u), (v), and (w), indicating that there is an edge between nodes (u) and (v) with weight (w).

The following (m) lines each contain two integers (l) and (r), specifying a query.

outputFormat

For each query, output a single integer — the number of distinct (dep(lca(i,j))) values among all pairs of nodes (i, j) with (l \le i, j \le r).

sample

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

3
5
1