410686: GYM104076 L Tree Distance

Memory Limit:512 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

L. Tree Distancetime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

You are given an unrooted weighted tree $$$T$$$ with vertices $$$1, 2, \ldots, n$$$. Please answer some queries.

We define $$$\texttt{dist}(i,j)$$$ as the distance between vertex $$$i$$$ and vertex $$$j$$$ in $$$T$$$.

For each query, you are given two integers $$$l, r$$$. Please answer the value of

$$$$$$\min_{l\le i< j\le r}(\texttt{dist}(i,j)).$$$$$$

Input

The first line contains one integer $$$n~(1\leq n\le 2 \times 10^5)$$$, the number of vertices in the tree.

Each of the next $$$n-1$$$ lines describes an edge of the tree. Edge $$$i$$$ is denoted by three integers $$$a_i, b_i, w_i$$$ $$$(1\le a_i, b_i\le n, 1\le w_i\le 10^9)$$$, the labels of vertices it connects and its weight.

Then one line contains one integer $$$q~(1\leq q\le 10^6)$$$, the number of queries.

Each of the following $$$q$$$ lines contains two integers $$$l, r~(1\le l \le r\le n)$$$ describing a query.

It is guaranteed that the given edges form a tree.

Output

For each query, output the answer in one line. If there is no $$$i,j$$$ such that $$$1\le i<j\le r$$$, the answer is $$$-1$$$.

ExampleInput
5
1 2 5
1 3 3
1 4 4
3 5 2
5
1 1
1 4
2 4
3 4
2 5
Output
-1
3
7
7
2

加入题单

上一题 下一题 算法标签: