All Tracks Data Structures Advanced Data Structures Segment Trees Problem

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, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?