A and B and Lecture Rooms

题面翻译

题目描述

A和B在准备参加编程比赛。

A和B学习的大学的房间由走廊连接。大学一共有$n$ 个房间，由$n-1$ 条走廊连接，房间的编号是从$1$ 到$n$ 的数字编号。

A和B在大学的某些房间里进行比赛。在每场比赛之后，他们会一起在一个房间里讨论问题。A和B希望这个讨论问题的房间到分别他们两个人比赛房间的距离相等。两个房间之间的距离指他们之间最短路的边数。

因为A和B每天都在不一样的房间里比赛，所以他们请求你告诉他们在接下来比赛的$m$ 天里可以用来讨论问题的房间有多少个？

输入输出格式

输入格式

第一行包括整数$n$ ，其中$(1<=n<=10^5)$ ，表示房间数量。

接下来的$n-1$ 行描述所有的走廊。这$n-1$ 行中的第$i$ 行包括两个整数$a_i$ 和$b_i$ ，表示第$i$ 条走廊连接了房间$a_i$ 和$b_i$ 。

接下来的一行输入比赛的天数$m(1<=m<=10^5)$ 。

再接下来的$m$ 行，第$j$ 行包含两个整数$x_j$ 和$y_j(1<=x_j,y_j<=n)$ ，表示比赛的第$j$ 天A将在$x_j$ 房间比赛，B将在$y_j$ 房间比赛。

输出格式

在第$i(1<=i<=m)$ 行输出当天分别到A、B比赛的房间距离相等的房间数量。

感谢@lonelysir 提供的翻译

题目描述

A and B are preparing themselves for programming contests.

The University where A and B study is a set of rooms connected by corridors. Overall, the University has $n$ rooms connected by $n-1$ corridors so that you can get from any room to any other one by moving along the corridors. The rooms are numbered from $1$ to $n$ .

Every day А and B write contests in some rooms of their university, and after each contest they gather together in the same room and discuss problems. A and B want the distance from the rooms where problems are discussed to the rooms where contests are written to be equal. The distance between two rooms is the number of edges on the shortest path between them.

As they write contests in new rooms every day, they asked you to help them find the number of possible rooms to discuss problems for each of the following $m$ days.

输入格式

The first line contains integer $n$ ( $1<=n<=10^{5}$ ) — the number of rooms in the University.

The next $n-1$ lines describe the corridors. The $i$ -th of these lines ( $1<=i<=n-1$ ) contains two integers $a_{i}$ and $b_{i}$ ( $1<=a_{i},b_{i}<=n$ ), showing that the $i$ -th corridor connects rooms $a_{i}$ and $b_{i}$ .

The next line contains integer $m$ ( $1<=m<=10^{5}$ ) — the number of queries.

Next $m$ lines describe the queries. The $j$ -th of these lines ( $1<=j<=m$ ) contains two integers $x_{j}$ and $y_{j}$ ( $1<=x_{j},y_{j}<=n$ ) that means that on the $j$ -th day A will write the contest in the room $x_{j}$ , B will write in the room $y_{j}$ .

输出格式

In the $i$ -th ( $1<=i<=m$ ) line print the number of rooms that are equidistant from the rooms where A and B write contest on the $i$ -th day.

样例 #1

样例输入 #1

4
1 2
1 3
2 4
1
2 3

样例输出 #1

1

样例 #2

样例输入 #2

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

样例输出 #2

0
2

提示

in the first sample there is only one room at the same distance from rooms number 2 and 3 — room number 1.