题目描述

给定一棵 $n$ 个点的树，$Q$ 个询问，每次询问点 $x$ 到点 $y$ 两点之间的距离。

树是一种无环连通图，树上两点间的距离定义为连接这两点的唯一简单路径上的边数。

---

输入格式

第一行一个正整数 $n$，表示这棵树有 $n$ 个节点；

接下来 $n-1$ 行，每行两个整数 $x, y$，表示 $x$ 和 $y$ 之间有一条边；

然后一个整数 $Q$，表示有 $Q$ 个询问；

接下来 $Q$ 行，每行两个整数 $x, y$，表示询问 $x$ 到 $y$ 的距离。

---

输出格式

输出 $Q$ 行，每行表示每个询问的答案。

---

样例

输入样例 1

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

输出样例 1

3
4

样例解释

树的结构如下（括号内为节点编号）：

       1
     /   \
    2     3
   / \     \
  4   5     6

• 询问 $2$ 到 $6$：路径为 $2 \to 1 \to 3 \to 6$，边数为 $3$。
• 询问 $5$ 到 $6$：路径为 $5 \to 2 \to 1 \to 3 \to 6$，边数为 $4$。

---

数据范围

• $1 \le n \le 10^5$
• $1 \le Q \le 10^5$
• $1 \le x, y \le n$

时间限制：1000 ms
内存限制：524288 KB

---

提示

这是一道最近公共祖先（LCA） 的模板题。

对于树上任意两点 $u, v$，设它们的最近公共祖先为 $lca(u, v)$，则它们之间的距离为：

$$dist(u, v) = depth[u] + depth[v] - 2 \times depth[lca(u, v)]$$

其中 $depth[x]$ 表示节点 $x$ 到树根的边数。

因此，可以先用一次 DFS 或 BFS 预处理出每个节点的深度 $depth$ 和父节点信息，然后用倍增、Tarjan 离线算法或树链剖分等方法预处理 LCA 查询。对于 $n, Q$ 达到 $10^5$ 的数据规模，建议使用倍增法（时间复杂度 $O((n+Q)\log n)$）或树链剖分（时间复杂度 $O(n + Q\log n)$）。