Neighbourhood Distance Sum on a Tree

Given a rooted tree with n nodes (numbered from 1 to n, with node 1 as the root), each node i is associated with a tuple \( (dep_i, str_i) \) where:

• \( dep_i \) is the distance (i.e. the number of edges) from node i to the root.
• \( str_i \) is the string formed by concatenating in order the node numbers along the simple path from the root to i.

You are given q queries. Each query consists of two integers \( x \) and \( k \). For each query, let \( S \) be the set of nodes in the \( (x,k) \) neighbourhood (i.e. all nodes whose distance from \( x \) is at most \( k \)). Sort the nodes in \( S \) in ascending order by their tuple \( (dep, str) \); that is, nodes are ordered primarily by \( dep \) and secondarily by lexicographic order of \( str \). Define

[ f(x,k)=\sum_{i=1}^{|S|-1}\operatorname{Dis}(c_i,c_{i+1}) ]

where \( c_1, c_2, \dots, c_{|S|} \) are the sorted nodes and \( \operatorname{Dis}(u,v) \) is the number of edges on the unique simple path between nodes \( u \) and \( v \).

Note:

• The \( (u,d) \) neighbourhood of a node \( u \) is defined as the set of nodes whose distance from \( u \) is \( \le d \).
• The distance between two nodes \( u \) and \( v \) is computed using the formula \( \operatorname{Dis}(u,v)=dep_u+dep_v-2\,dep_{\operatorname{LCA}(u,v)} \), where \( \operatorname{LCA}(u,v) \) is the lowest common ancestor of \( u \) and \( v \).

inputFormat

The first line contains two integers n and q, representing the number of nodes in the tree and the number of queries, respectively.

The next n-1 lines each contain two integers u and v, denoting an undirected edge between nodes u and v. The tree is rooted at node 1.

The following q lines each contain two integers x and k representing a query.

outputFormat

For each query, output the value of \( f(x,k) \) on a separate line.

sample

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

4
3