P9058 [Ynoi2004] rpmtdq

Given an unrooted tree with edge weights, you need to answer some queries. Define $\texttt{dist(i,j)}$ as the distance between node $i$ and node $j$ on the tree. For each query, you are given $l, r$. You need to output $\min(\texttt{dist(i,j)})$ where $l \le i < j \le r$.

The first line contains an integer $n$, denoting the number of nodes in the tree. The next $n - 1$ lines each contain three integers $x, y, z$, representing a tree edge connecting $x$ and $y$ with weight $z$. The input is guaranteed to form a tree. Then there is a line containing an integer $q$, denoting the number of queries. The next $q$ lines each contain two integers $l, r$, representing a query. If for a query, there is no pair $(i, j)$ satisfying $l \le i < j \le r$, output $-1$.

Output $q$ lines. Each line contains one integer, denoting the answer to the corresponding query.

Idea: nzhtl1477, Solution: Kubic&ccz181078, Code: Kubic, Data: Kubic. For $100\%$ of the testdata, $n \le 2 \times 10^5$, $q \le 10^6$, and $1 \le z \le 10^9$. Translated by ChatGPT 5