Christmas tree
Tag(s):

## Algorithms, DFS, Medium-Hard

Problem
Editorial
Analytics

Little Santa have to give gifts to N children. There are $N-1$ roads connecting the homes of N children. Each road has some special Santa tax value which only Santa have to pay. Little Santa is wondering what is the $realK^{th}$ minimum tax value in the path between the home of child $realA$ and child $realB$.

Note: $k^{th}$ minimum value in a list A is $k^{th}$ value in the list A after sorting A.

Input format:
First line contains one integer, N $(2 \leq N \leq 7.5 * 10^5)$, denoting the number of children. Next $N-1$ lines contains three space separated integers each, $x, y, w$ $(1 \le x, y \le N), (0 \le w \le 10^9)$, denoting that home of child x is connected to home of child y and the tax value of the road is w. Next line will contain an integer, q $(1 \le q \le 7.5*10^5)$, denoting the number of queries. Next q lines contains three space separated integers each, $a, b$ $(1 \le a, b \le N)$ and k $(1 \le k \le N-1)$.

To generate $realA$ and $realB$ you have to use following formulas:

• $realA_i = ((a_i - 1 + max(0, lastAns)) \mod n) + 1$
• $realB_i = ((b_i - 1 + 2 * max(0, lastAns)) \mod n) + 1$
• $realK_i = ((k_i - 1 + 3 * max(0, lastAns)) \mod n) + 1$

Where $lastAns$ is answer for previous query, or 0 if this is the first query.

Output format:
For each query, print the number the $realK^{th}$ minimum tax value in the path between the home of child $realA$ and child $realB$. Print 1 if there is no such value.

SAMPLE INPUT
5
1 2 1
1 3 2
2 4 3
2 5 3
3
4 5 1
5 3 2
4 5 3
SAMPLE OUTPUT
3
1
3
Explanation

Here are the real values for queries from sample:

$realA_1 = 4, realB_1 = 5, realK_1 = 1$

$realA_2 = 3, realB_4 = 4, realK_2 = 1$

$realA_3 = 5, realB_3 = 2, realK_3 = 1$

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 512 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...

## This Problem was Asked in

Challenge Name

Christmas Circuits '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming
• Algorithms > String Algorithms