P6589 "JROI-1" Relationship Tree

Xiao L has many favorite game characters, and he connects these characters according to certain relationships. These characters and their relationships form a tree, which Xiao L calls the "relationship tree".

A relationship tree is a tree consisting of $n$ vertices and $n - 1$ undirected edges. For a given graph $G$, define the **vertex-induced subgraph** of $G$ on a vertex set $E$ as the graph consisting of the vertex set $E$ and all edges in the original graph $G$ whose **both endpoints belong to $E$**. A graph is defined to be **clean** if and only if for any two vertices $u, v$ in the graph, either $u$ and $v$ are **not connected**, or the **distance is at most** $k$. Xiao L wants to know, for a query pair $l, r$ ($l \leq r$), how many pairs $(a, b)$ satisfy $l \leq a \leq b \leq r$, such that the vertex-induced subgraph formed by all vertices with indices from $a$ to $b$ (including $a, b$) is **clean**. Moreover, he also wants you to output the sum of all interval lengths (i.e., $b - a + 1$). Since Xiao L likes asking questions, you need to answer a total of $q$ queries.

The first line contains three integers $n$, $q$, $k$, with the meanings as described above. The next $n - 1$ lines each contain two integers $u$, $v$, describing an edge. The next $q$ lines each contain two integers $l$, $r$, representing a query.

Output $q$ lines. Each line contains two integers: the number of valid pairs $(a, b)$, and the sum of all interval lengths.

#### Sample 1 Explanation The relationship tree formed is shown in the figure.  The valid $(a, b)$ are $(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(2,5),(3,3),(3,4),(3,5),(4,4),(4,5),(5,5)$. The answers to the three queries are $6,10$, $10,20$, and $14,30$, respectively. -------------------------------- #### Constraints **This problem uses bundled testdata.** + Subtask 1 ( $10\%$ ): $n \leq 2000$. + Subtask 2 ( $30\%$ ): $n \leq 2 \times 10^4$, and the relationship tree is a chain. + Subtask 3 ( $60\%$ ): $n \leq 2 \times 10^4$. + Subtask 4 ( Enhanced version testdata, time limit $4.5s$ ): No special restrictions. For all test cases ($100\%$), it is guaranteed that $1 \leq n \leq 8 \times 10^4$, $1 \leq q \leq 10^5$, $0 \leq k < n$, $1 \leq u, v, l, r \leq n$. Translated by ChatGPT 5