시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 512 MB104433043.478%

문제

트리에 팔을 만들어주자.

트리의 팔을 다음과 같이 정의하자.

  • 임의의 트리 $T$에 대해 트리의 양팔은 루트 노드 $R$에서 도달 가능한 리프노드 $a$, $b$ 한 쌍을 의미한다. 즉, 트리의 양팔은 리프노드 순서쌍 $(a, b)$이다.
  • 트리의 양팔이 $(a, b)$일 때, 왼쪽 팔은 $a$이고 오른쪽 팔은 $b$이다.
  • 오른팔과 왼팔은 같을 수 있다. 즉, $(a, a)$도 유효한 양팔이다.
  • 이때, 어떤 한쪽 팔의 길이는 루트 노드 $R$에서부터의 최단 거리로 정의한다.

어떤 트리 $T$가 주어졌을 때, 해당 트리가 가질 수 있는 양팔을 $(a, b)$라고 했을 때, 양팔의 길이의 합이 $W$이상 $V$이하가 되는 순서쌍 $(a, b)$의 개수를 구하는 $Q$개의 쿼리를 처리해보자.

입력

첫 번째 줄에 트리의 정점 개수 $N$, 루트 노드의 번호 $R$이 주어진다. $(2 \le N \le 300\ 000; 1 \le R \le N)$

두 번째 줄부터 $N - 1$개의 줄에 걸쳐 연결된 두 정점 $u, v$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N)$

$N + 2$ 번째 줄에는 처리해야할 쿼리의 개수 $Q$가 주어진다. $(1 \le Q \le 200\ 000)$

$N + 3$ 번째 줄부터 한 줄에 쿼리가 하나씩 주어진다. 각 쿼리의 $W, V$가 공백으로 구분되어 들어오는 형태이다. $(1 \le W \le V \le N)$

출력

양팔의 길이 합이 $W$이상 $V$이하가 되는 순서쌍 $(a, b)$의 개수를 구해 $1\ 000\ 000\ 007$로 나눈 나머지를 쿼리별로 한 줄마다 출력한다.

예제 입력 1

8 4
1 4
2 6
3 4
3 5
1 7
4 6
4 8
1
3 4

예제 출력 1

15

출처

University > 한양대학교 > 제9회 한양대학교 프로그래밍 경시대회 > Advanced Division I번