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