Joseph and Tree
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
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++,
Clojure,
C#,
D,
Erlang,
F#,
Go,
Groovy,
Haskell,
Java,
Java 8,
JavaScript(Rhino),
JavaScript(Node.js),
Lisp,
Lisp (SBCL),
Lua,
Objective-C,
OCaml,
Octave,
Pascal,
Perl,
PHP,
Python,
Python 3,
R(RScript),
Racket,
Ruby,
Rust,
Scala,
Scala 2.11.8,
Swift,
Visual Basic