Tree Query: Sum of Distances

You are given a tree with \( n \) nodes numbered from \( 1 \) to \( n \), and \( n-1 \) edges connecting them. The distance \( d(a,b) \) between two nodes \( a \) and \( b \) is defined as the smallest non-negative integer \( k \) for which there exists a sequence of nodes \( v_0, v_1, \dots, v_k \) such that \( v_0 = a \), \( v_k = b \), and for each \( 0 \le i < k \), there is an edge between \( v_i \) and \( v_{i+1} \) in the tree.

You are also given \( m \) queries. Each query contains four parameters \( p_0, d_0, p_1, d_1 \). For each query, you are to compute the sum:

[ S = \sum_{\substack{a=1 \ d(p_0,a) \le d_0}} ; \sum_{\substack{b=1 \ d(p_1,b) \le d_1}} d(a,b) ]

Note: It is guaranteed that the tree has at most 200 nodes and the number of queries does not exceed 200.

inputFormat

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

Each of the next \( n-1 \) lines contains two integers \( u \) and \( v \) representing an edge between nodes \( u \) and \( v \).

Then \( m \) lines follow, each containing four integers \( p_0, d_0, p_1, d_1 \) representing a query.

outputFormat

For each query, output one line containing the sum \( S \) as defined above.

sample

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

17
20