32998번 - 정기 모임 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$)