Description

Let $\text T$ be a rooted tree. We make the following definitions:

• Let $a$ and $b$ be two distinct nodes in $\text T$. If $a$ is an ancestor of $b$, then we say "$a$ is more formidable than $b$."
• Let $a$ and $b$ be two distinct nodes in $\text T$. If the distance between $a$ and $b$ in the tree is no more than a given constant $x$, then we say "$a$ and $b$ are about the same."

Given a rooted tree $\text T$ with $n$ nodes, numbered from $1$ to $n$, where the root is node $1$. You need to answer $q$ queries. In each query, two integers $p$ and $k$ are given. Determine how many ordered triples $(a, b, c)$ satisfy:

1. $a, b, c$ are three distinct nodes in $\text T$, and $a$ is node $p$.
2. $a$ and $b$ are both more formidable than $c$.
3. $a$ and $b$ are about the same, where the constant in “about the same” is the given $k$.

Input Format

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

The next $n - 1$ lines each describe an edge of the tree. Each line contains two integers $u$ and $v$, indicating that there is an edge between nodes $u$ and $v$.

The next $q$ lines each describe an operation. The $i$-th line contains two integers, representing $p$ and $k$ for the $i$-th query.

Output Format

Output $q$ lines. Each line corresponds to a query and contains the answer to that query.

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

3
1
3

Hint

The tree in the sample is shown below:

For the first and third queries, the valid triples are $(2,1,4)$, $(2,1,5)$, and $(2,4,5)$.

For the second query, the only valid triple is $(4,2,5)$.

The constraints for all test points are as follows (note that Luogu does not evaluate according to the following):

For all queries in the full testdata, $1 \le p, k \le n$.

• On 2023.9.15, a set of hack testdata was added.

Translated by ChatGPT 5