Tree Distance Sum Queries

Given a tree of n nodes numbered from 1 to n, where the distance between two nodes a and b is defined as the smallest non-negative integer k such that there exists a sequence of nodes \(v_0, v_1, \ldots, v_k\) with \(v_0 = a\) and \(v_k = b\) and an edge connecting \(v_i\) and \(v_{i+1}\) for every \(0 \le i \le k-1\).

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

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

Note: It is guaranteed that the input tree is connected.

inputFormat

The input is given as follows:

1. An integer n representing the number of nodes.
2. Next n-1 lines, each containing two integers u and v, denoting an edge between nodes u and v.
3. An integer m representing the number of queries.
4. Next m lines, each containing four integers: p₀, d₀, p₁ and d₁.

You may assume that the tree has small size so that an \(O(n^2)\) solution is acceptable.

outputFormat

For each query, output a single integer — the value of the sum \(S\) as defined above. Each answer should be printed on a new line.

sample

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

17