Joseph and Tree
Tag(s):

## Data Structures, Medium, Segment Trees, Trees

Problem
Editorial
Analytics

Joseph loves games about a tree! His friend Nick invented a game for him!

Initially, there is a rooted weighted tree with $N$ vertices numbered $1\dots N$ . Nick guarantees that the tree is connected, and there is a unique path between any vertices! Also he gave us $Q$ queries on it of following type:

• $v$ and $k$ : Let $S$ denote the sorted (non decreasing order) array of shortest distances from $v$ to any other vertex from subtree rooted $v$. Answer will be $k_{th}$ element of $S$. If such a number does not exist, i.e. the $S$ has less than $k$ elements, answer is $-1$. Note that $v$ is not included in his own subtree.

All the indices in the queries are 1-based. Root of the tree is node $1$.

But it turns out, Joseph has an exam tomorrow, and he doesn't have time for playing a game! And he asks your help!

Input format

The first line contains a single integer $N$ denoting the number of vertices of the tree.

The next $N - 1$ lines contain three integers $a_i, b_i$ and $w_i$, denoting that there is an edge between vertices $a_i$ and $b_i$ with weight $w_i$.

The next line contains a single integer $Q$ denoting the number of queries.

The next $Q$ lines contain two integers $v_i$ and $k_i$, denoting the query described above.

Output format

Print the answer for each query. Note that if there is no such element, print $-1$.

Constraints

• $1 ≤ N, Q ≤ 10^5$
• $1 ≤ a_i, b_i, v_i ≤ N; a_i \neq b_i$
• $1 ≤ w_i, k_i ≤ 10^9$

Subtasks

• Subtask #1 (30 points) : $1 ≤ N, Q ≤ 2000$
• Subtask #2 (70 points) : Original constraints
SAMPLE INPUT
7
2 1 3
1 3 1
2 4 2
3 5 5
3 6 1
7 3 2
5
1 3
2 1
2 2
3 2
6 4

SAMPLE OUTPUT
3
2
-1
2
-1
Explanation
• In the first query, $v = 1$ and $S =${$1, 2, 3, 3, 5, 6$}, thus $k_{th}$ element, i.e. $3_{rd}$ element is equal to $3$.
• In the second query, $v = 2$ ans $S=${$2$}, thus answer is $2$.
• In the third query, $v = 2$ but size of $S$ is less than $2$, thus answer is $-1$.
Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...
Your Rating:

## This Problem was Asked in

Challenge Name

August Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Number Theory
• Data Structures > Advanced Data Structures
• Algorithms > Graphs
• Data Structures > Advanced Data Structures
Notifications