Informatica Online Judge

  형평성 [2133 / 0855]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 2   Total Tried : 2


The Champion of this Problem (C++) : gs16109 - 6ms / 1403byte
My Best Submission (C++) : N/A

[34th 노규민]
Writer ID : [gs16030]

Background

어느 별에 있는 어떤 나라 X는 교육열과 지역 간의 라이벌 의식이 매우 심하기로 유명하다.

나라 X는 지역이 N개 있고, 지역 간의 양방향 도로가 N-1개 있는 트리 형태를 가지고 있다.

각 도로의 길이는 모두 1이다.

나라 의 정부에서는 첫눈을 맞아, 지역 간/지역 내 정보과학 대회를 총 Q개 개최하기로 결정하였다.

각 대회에서는 두 지역 u와 v의 학생들이 실력을 겨루는데, 형평성을 위해서 이 대회의 개최지 w를 정할 때, 지역 u, w사이의 최단거리와 지역 v, w사이의 최단거리가 같도록 하기로 결정하였다.

u=v인 경우도 존재하는데, 이는 지역 내 대회고, 개최지 w는 같은 조건하에 결정한다.

나라 의 정부는 무능해서, 가능한 개최지의 수를 구하지도 못했다.
각 Q개의 대회에 대한 가능한 개최지의 수를 전부 구하자.

Input

첫 줄에는 지역의 개수 N과 대회의 수 Q가 들어온다. 2<=N, Q<=100000

다음 N-1개의 줄에는 지역 간 도로 정보가 x, y로 주어진다. 1<=x, y <=N

다음 Q개 줄에는 두 지역 u, v가 주어진다.
1<=u, v<=N이고 u=v일 수 있다.

Output

각 Q개의 대회에서 가능한 개최지의 수를 각 줄마다 하나씩 출력한다.

IO Example

입력
6 5
1 2
1 3
2 4
2 5
3 6
2 5
2 6
2 3
4 6
4 5

출력
0
0
1
1
4

설명
첫 번째 쿼리, 두 번째 쿼리에는 가능한 개최지가 없다.

세 번째 쿼리에서는 1번 지역이 가능하다. 2,3번 지역과 거리가 모두 1이다.

네 번째 쿼리에서는 1번 지역이 가능하다. 4,6번 지역과 거리가 모두 1이다.

마지막 쿼리에서는 1,2,3,6번 지역이 가능하다.
1번 지역은 4,5번 지역과 거리가 모두 2다.
2번 지역은 거리가 모두 1이다.
3번 지역은 거리가 모두 3이고, 6번 지역은 거리가 모두 4다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]