Regular meeting 6

Gyeonggak village has a tree structure. The village is so large that the tree can have up to $10^9$ vertices. The input format is described below.

$M$ residents live in Gyeonggak village. Each resident is given a distinct number from 1 to $M$. The residents plan to hold $Q$ regular meetings.

Resident $i$ lives in vertex $x_i$. Several residents can live in the same vertex. Residents dislike traveling far, so resident $i$ can move at most $d_i$ away from home. The distance between two vertices is the minimum number of edges on a path between them.

Each regular meeting involves residents $l_i$ through $r_i$. For each meeting, find the number of vertices where all participating residents can gather.

The first line contains three integers $N$, $M$, and $Q$. $N$ is the initial number of vertices, $M$ is the number of residents, and $Q$ is the number of regular meetings.

From the second line onward, the next $N-1$ lines describe the tree. The $i$-th line contains three integers $u_i$, $v_i$, and $c_i$. This means that $c_i$ new vertices are added on the path between vertices $u_i$ and $v_i$.

The new vertices are created as follows. The $c_i$ vertices created by the $i$-th input are connected in order from $u_i$ toward $v_i$. Their numbers run from $N + \sum_{j=1}^{i-1} c_j + 1$ to $N + \sum_{j=1}^{i} c_j$ in sequence.

The given edges are guaranteed to form a single tree.

The next $M$ lines describe the residents. The $i$-th line contains two integers $x_i$ and $d_i$. This means resident $i$ lives in vertex $x_i$ and can move at most $d_i$.

The next $Q$ lines describe the meetings. The $i$-th line contains two integers $l_i$ and $r_i$. This means residents $l_i$ through $r_i$ take part in that meeting.

Print $Q$ lines. On the $i$-th line, print the number of vertices that all residents taking part in the $i$-th meeting can reach.

• $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$)