Problem Description

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$.

Input Format

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 Format

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

5
1 2 5
1 3 3
1 4 4
3 5 2
5
1 1
1 4
2 4
3 4
2 5

-1
3
7
7
2

Hint

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