18794번 - 트리와 쿼리 15

문제

N개의 정점으로 이루어진 트리가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있다. 간선의 가중치는 모두 1이다.

아래의 쿼리를 수행하는 프로그램을 작성하시오.

• k v₁ r₁ v₂ r₂ ... v_k r_k: 어떠한 정점 x가 v_i와 거리 r_i 이내에 있다면 (거리가 r_i보다 작거나 같다면), x가 i번 조건을 만족한다고 하자. 트리에 있는 모든 정점들 중, 쿼리로 주어진 k개 조건 중 1개 이상의 조건을 만족하는 정점의 개수를 출력하라.

​​​​​​

입력

첫 번째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 100,000)

이후 N-1개의 줄에는 각 간선이 연결하는 두 정점 번호 u, v가 주어진다. (1 ≤ u, v ≤ N)

다음 줄에 정수 M이 주어진다. (1 ≤ M ≤ 300,000)

이후 M개의 줄에 위에서 설명한 것과 같은 쿼리가 주어진다. 각 쿼리는 지문과 다르게 한 줄에 들어오지 않으며, k + 1개의 줄로 분리되어 주어진다. 예제 입력을 참고하라. (1 ≤ v_i ≤ N, 0 ≤ r_i < N, 1 ≤ k)

쿼리로 주어지는 k의 합은 300000을 넘지 않는다.

출력

쿼리의 결과를 한 줄에 하나씩 출력한다.

제한

힌트