P3899 [Hunan Training Camp] Even More Formidable

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$.

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 $q$ lines. Each line corresponds to a query and contains the answer to that query.

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