정기 모임 6

경곽마을은 트리 구조이다. 이 마을은 매우 거대하여 트리의 정점이 $10^9$개까지 존재할 수 있다. 자세한 입력 방법은 아래에서 설명한다.

경곽마을에는 $M$명의 주민이 살고 있으며, 각 주민은 1부터 $M$까지 서로 다른 번호를 받는다. 주민들은 정기 모임을 $Q$번 열려고 한다.

$i$번 주민은 정점 $x_i$에 집이 있으며, 그곳에 살고 있다. 한 정점에 여러 주민이 함께 살 수 있다. 주민들은 먼 거리를 이동하는 것을 선호하지 않아서, 각자 자신의 집에서 최대 $d_i$만큼 이동할 수 있다. 두 정점 사이의 거리는 한 정점에서 다른 정점으로 이동할 때 거쳐야 하는 최소 간선의 수로 정의한다.

각 정기 모임에는 $l_i$번 주민부터 $r_i$번 주민까지 참여한다. 각 모임마다 참여하는 모든 주민이 모일 수 있는 정점의 개수를 구한다.

첫 번째 줄에 세 정수 $N$, $M$, $Q$가 공백으로 구분되어 주어진다. $N$은 초기 정점의 수, $M$은 주민의 수, $Q$는 정기 모임의 횟수이다.

두 번째 줄부터 $N-1$개의 줄에 트리의 구조가 주어진다. $i$번째 줄에는 세 정수 $u_i$, $v_i$, $c_i$가 공백으로 구분되어 주어지며, 이는 정점 $u_i$와 $v_i$를 잇는 경로 위에 새로운 정점이 $c_i$개 추가됨을 뜻한다.

새로운 정점은 다음 규칙으로 생성된다. $i$번째 입력에서 생성되는 $c_i$개의 정점은 $u_i$에서 $v_i$ 방향으로 순서대로 연결되며, 번호는 $N + \sum_{j=1}^{i-1} c_j + 1$부터 $N + \sum_{j=1}^{i} c_j$까지 차례로 부여된다.

주어지는 간선 정보는 반드시 하나의 트리를 이루도록 보장된다.

그다음 $M$개의 줄에 각 주민의 정보가 주어진다. $i$번째 줄에는 두 정수 $x_i$와 $d_i$가 공백으로 구분되어 주어지며, 이는 $i$번 주민이 정점 $x_i$에 살고 있고 최대 $d_i$만큼 이동할 수 있음을 뜻한다.

그다음 $Q$개의 줄에 각 정기 모임의 정보가 주어진다. $i$번째 줄에는 두 정수 $l_i$와 $r_i$가 공백으로 구분되어 주어지며, $l_i$번 주민부터 $r_i$번 주민까지 해당 모임에 참여함을 뜻한다.

$Q$개의 줄에 걸쳐 답을 출력한다. $i$번째 줄에는 $i$번째 정기 모임에 참여하는 모든 주민이 도달할 수 있는 정점의 개수를 출력한다.

• $1 \leq N, M, Q \leq 100\,000$
• $1 \leq u_i, v_i \leq N$ ($1 \leq i \leq N-1$)
• $u_i \neq v_i$ ($1 \leq i \leq N-1$)
• $c_i \geq 0$ ($1 \leq i \leq N-1$)
• $N + \sum_{i=1}^{N-1} c_i \leq 10^9$
• $1 \leq x_i \leq N + \sum_{j=1}^{N-1} c_j$ ($1 \leq i \leq M$)
• $1 \leq d_i \leq 10^9$ ($1 \leq i \leq M$)
• $1 \leq l_i \leq r_i \leq M$ ($1 \leq i \leq Q$)