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 one node selected as the root.

Let T be a tree, and let Tr be that tree rooted at node r. The subtree of u in Tr is the set of all nodes v such that the path from r to v contains u (including u itself). In this problem, the set of nodes in the subtree of u in the tree rooted at r is written Tr(u).

You are given q queries. Each query consists of two nodes r and p, which may be the same. A set S is “obtainable” 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, S is obtainable if there exist nodes u and v with S = Tr(u) ∩ Tp(v).

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

The first line contains two space-separated integers n and q (1 ≤ n, q ≤ 2 · 105). n is the number of nodes in the tree, and q is the number of queries to answer. The nodes are numbered from 1 to n.

Each of the next n − 1 lines contains two space-separated integers u and v (1 ≤ u, v ≤ n, u ≠ v), which represent an undirected edge between nodes u and v. These edges are guaranteed to form a valid tree.

Each of the next q lines contains two space-separated integers r and p (1 ≤ r, p ≤ n), the root nodes for that query.

For each query, print one integer on its own line: the number of distinct obtainable sets of nodes that can be produced by the procedure above.

The possible rootings of the first tree are shown below.

With roots 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.

With roots at 4 and 5 instead, 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, other choices of u and v lead to the same set.