Description

一家航空公司运营着涉及 $n$ 个不同机场的定期航班。每条航班直接连接两个机场（即中间不经停其他机场），并且允许双向通行。航班的安排方式保证了：对于任意选择的起点机场 $s$ 和终点机场 $t$，存在且仅存在一条不重复经过任何机场的航班序列将两者连接起来。该序列中航班的数量被称为 $s$ 到 $t$ 的距离。

如果航空公司再新增一条航班，比如在机场 $x$ 和 $y$ 之间，则可能会出现对于某些 $(s, t)$ 对，存在另一条更短的航班序列将 $s$ 和 $t$ 连接起来。受影响的 $(s, t)$ 对越多，说明在 $x$ 和 $y$ 之间新增航班的价值越大。航空公司希望你帮助他们评估若干个可能新增的 $(x, y)$ 航班在这一标准下的表现。

Input Format

第一行包含两个整数 $n,q$，表示机场的数量和询问的次数。

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示有一条航班直接连接机场 $u_i$ 和 $v_i$。

接下来 $q$ 行，每行包含两个整数 $x_i$ 和 $y_i$，表示询问如果在机场 $x_i$ 和 $y_i$ 之间新增一条航班，会有多少对 $(s, t)$ 的最短距离变短。

Output Format

输出 $q$ 行，第 $i$ 行输出一个整数，表示满足 $1 \leq s < t \leq n$ 且在原有 $n-1$ 条航班的网络基础上，若补充一条 $x_i$ 和 $y_i$ 之间的直达航班后，$s$ 到 $t$ 的距离会变短的 $(s, t)$ 对数。

8 2
1 5
5 2
7 3
3 8
6 4
4 5
6 3
5 7
2 6

10
4

Hint

输入限制

• $2 \leq n \leq 10^6$
• $1 \leq q \leq 10^5$
• $1 \leq u_i \leq n; 1 \leq v_i \leq n; u_i \neq v_i$
• $1 \leq x_i \leq n; 1 \leq y_i \leq n; x_i \neq y_i$
• $\sum_{i=1}^{q} d_i \leq 10^7$，其中 $d_i$ 表示原航班网络中 $x_i$ 和 $y_i$ 之间的距离。

由 ChatGPT 4.1 翻译