#E. 树上两点距离

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一棵n个点构成的树，以及m次询问，每次给出树上两个点a和b，求a和b之间的距离为多少（每条边的边权都为1）

第一行给定一个整数 $n$ ,

接下来 $n - 1$ 行，每行给出两个整数 $u, v$ ，代表 $u, v$ 之间存在一条边

接下来一行给出一个整数 $m$ , 代表有 $m$ 次询问

接下来 $m$ 行每行给出两个整数 $a, b$ ，代表一次询问，请你输出 $a$ 点和 $b$ 点之间的距离

输出一共 $m$ 行，对于每一个询问单独输出一行，输出 $a, b$ 点之间的距离

2
1

对于 50% 的测试样例， $1 \le n, m \le 1000$

对于100%的测试样例 $1 \le n, m \le 100000, 1 \le u, v, a, b \le n$