← 返回题目
题库练习 树上的距离
← 上一题 下一题 →

A71346 | 树上的距离

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

给定一棵树，树上有 n 个结点，结点编号为 1 \sim n 。

再给定 q 次询问，每次询问给定 2 个结点编号，请编程计算出这两个结点在树上的距离。

输入格式

第一行一个正整数 n，表示结点数量；

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

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

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

数据范围：

1≤n,q≤105，1≤x,y≤n；

输出格式

输出 q 行，每行一个整数，表示每次询问的答案。

输入输出样例

输入 #1
6
1 2
1 3
2 4
2 5
3 6
2
2 6
5 6
输出 #1
3
4
C++ 编辑器
输入
输出