Kattis

# Rooted Subtrees

A tree is a connected, acyclic, undirected graph with $n$ nodes and $n - 1$ edges. There is exactly one path between any pair of nodes. A rooted tree is a tree with a particular node selected as the root.

Let $T$ be a tree and $T_ r$ be that tree rooted at node $r$. The subtree of $u$ in $T_ r$ is the set of all nodes $v$ where the path from $r$ to $v$ contains $u$ (including $u$ itself). In this problem, we denote the set of nodes in the subtree of $u$ in the tree rooted at $r$ as $T_ r(u)$.

You are given $q$ queries. Each query consists of two (not necessarily different) nodes, $r$ and $p$. A set of nodes $S$ is “obtainable” if and only if it can be expressed as the intersection of a subtree in the tree rooted at $r$ and a subtree in the tree rooted at $p$. Formally, a set $S$ is “obtainable” if and only if there exist nodes $u$ and $v$ where $S = T_{r}(u) \cap T_{p}(v)$.

For a given pair of roots, count the number of different non-empty obtainable sets. Two sets are different if and only if there is an element that appears in one, but not the other.

## Input

The first line contains two space-separated integers $n$ and $q$ $(1 \le n, q \le 2 \cdot 10^5)$, where $n$ is the number of nodes in the tree and $q$ is the number of queries to be answered. The nodes are numbered from $1$ to $n$.

Each of the next $n - 1$ lines contains two space-separated integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$), indicating an undirected edge between nodes $u$ and $v$. It is guaranteed that this set of edges forms a valid tree.

Each of the next $q$ lines contains two space-separated integers $r$ and $p$ ($1 \le r,p \le n$), which are the nodes of the roots for the given query.

## Output

For each query output a single integer, which is the number of distinct obtainable sets of nodes that can be generated by the above procedure.

## Sample Explanation

The possible rootings of the first tree are

Considering the rootings at $1$ and $3$, the $8$ obtainable sets are:

1. $\{ 1\}$ by choosing $u = 1$, $v = 1$,

2. $\{ 1, 2, 4, 5\}$ by choosing $u = 1$, $v = 2$,

3. $\{ 1, 2, 3, 4, 5\}$ by choosing $u = 1$, $v = 3$,

4. $\{ 2, 3, 4, 5\}$ by choosing $u = 2$, $v = 3$,

5. $\{ 2, 4, 5\}$ by choosing $u = 2$, $v = 2$,

6. $\{ 3\}$ by choosing $u = 3$, $v = 3$,

7. $\{ 4, 5\}$ by choosing $u = 2$, $v = 4$,

8. and $\{ 5\}$ by choosing $u = 5$, $v = 5$.

If the rootings are instead at $4$ and $5$, there are only $6$ obtainable sets:

1. $\{ 1\}$ by choosing $u = 1$, $v = 1$,

2. $\{ 1, 2, 3\}$ by choosing $u = 2$, $v = 4$,

3. $\{ 1, 2, 3, 4\}$ by choosing $u = 4$, $v = 4$,

4. $\{ 1, 2, 3, 4, 5\}$ by choosing $u = 4$, $v = 5$,

5. $\{ 3\}$ by choosing $u = 3$, $v = 2$,

6. and $\{ 5\}$ by choosing $u = 5$, $v = 5$.

For some of these, there are other ways to choose $u$ and $v$ to arrive at the same set.

Sample Input 1 Sample Output 1
5 2
1 2
2 3
2 4
4 5
1 3
4 5

8
6