问题 1996. -- 点的距离

1996: 点的距离

时间限制: 1 Sec  内存限制: 128 MB
提交: 24  解决: 10
[提交][状态][讨论版]

题目描述

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

输入

第一行一个n，表示这棵树有n个结点。
接下来n−1行，每行两个整数x,y表示x,y之间有一条连边。
然后一个整数Q，表示有Q个询问。
接下来Q行，每行两个整数x,y表示询问x到y的距离。

输出

输出 Q 行，每行表示每个询问的结果。

样例输入

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

样例输出

3
4

提示

数据范围：1<=n<=100000, 1<=x,y<=n。

来源

倍增/LCA

[提交][状态]