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, 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