시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 104 | 43 | 30 | 43.478% |
트리에 팔을 만들어주자.
트리의 팔을 다음과 같이 정의하자.
어떤 트리 $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$로 나눈 나머지를 쿼리별로 한 줄마다 출력한다.
8 4 1 4 2 6 3 4 3 5 1 7 4 6 4 8 1 3 4
15
University > 한양대학교 > 제9회 한양대학교 프로그래밍 경시대회 > Advanced Division I번