最短距离

题目描述

给定一棵包含 $N$ 个节点的无根树，节点编号 $1\sim N$，定义两点距离 $d(x,y)$ 为 $x,y$ 树上最短路径的边数。

共有 $Q$ 次询问，每次给定两个节点 $u,v$，求：

输入格式

N
A1 B1
A2 B2
……
A_{N-1} B_{N-1}
Q
L1 R1
L2 R2
……
LQ RQ

输出格式

对于每次询问，输出一行对应答案。

输入输出样例 #1

输入 #1

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

输出 #1

4
6
3

输入输出样例 #2

输入 #2

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

输出 #2

14
16
10
16
14
16
8

说明/提示

数据范围

• $1 \le N,Q \le 2\times 10^5$
• $1\le A_i,B_i,L_i,R_i \le N$
• 保证输入为合法树结构，所有输入为整数

样例解释 1

以第一次询问 $(4,1)$ 为例： 对所有节点 $j$ 计算 $\min(d(j,4),d(j,1))$：

• $j=1:\min(2,0)=0$
• $j=2:\min(2,2)=2$
• $j=3:\min(1,3)=1$
• $j=4:\min(0,2)=0$
• $j=5:\min(1,1)=1$

总和 $0+2+1+0+1=4$，与输出一致。