Sloth Naptime

View as PDF

Submit solution


Points: 0.50 (partial)
Time limit: 5.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
https://codeforces.com/gym/102694/problem/C
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Như các bạn đã biết, lười sống trên cây. David có một chú lười làm thú cưng và anh thường cho nó chơi với những chiếc cây (không trọng số) trong khi anh giải các bài toán lập trình. Thỉnh thoảng, David thấy rằng chú lười đang đứng ở đỉnh ~a~ trên cây, và yêu cầu nó di chuyển đến một đỉnh ~b~ khác.

Đương nhiên, chú lười rất nghe lời David, nhưng lượng năng lượng còn lại chỉ cho phép nó di chuyển qua tối đa ~c~ cạnh. Nếu chú lười cần di chuyển qua ít hơn ~c~ cạnh để đến đỉnh ~b~, nó sẽ đến ~b~ và ngủ một giấc. Nếu không, chú lười sẽ đến gần ~b~ nhất có thể trước khi dừng lại và đứng yên tiêu hóa thức ăn.

Vậy chú lười sẽ dừng lại ở đâu? Vì chuyện này xảy ra khá thường xuyên, David muốn nhờ bạn trả lời ~q~ câu hỏi có dạng như nhau.

Input

Dòng đầu tiên chứa một số nguyên ~n~, là số đỉnh trên cây. ~n - 1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ và ~v~ miêu tả các cạnh trong cây. Dữ liệu đầu vào đảm bảo các cạnh này tạo thành một cây.

Dòng tiếp theo chứa một số nguyên ~q~, là số lần David sẽ yêu cầu chú lười di chuyển. ~q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~a~, ~b~, và ~c~ lần lượt là đỉnh mà chú lười đang đứng, đỉnh mà David yêu cầu chú lười di chuyển tới, và lượng năng lượng của chú lười khi bắt đầu di chuyển.

~1 \le n, q \le 3 \times 10^5~

~1 \le a, b, c, u, v \le n~

Output

Với mỗi câu hỏi, in ra một số nguyên là số thứ tự của đỉnh mà chú lười sẽ dừng lại sau câu hỏi đó.

Sample 1

Input
1
1
1 1 1
Output
1

Sample 2

Input
3
3 2
2 1
3
2 2 2
1 1 2
3 3 3
Output
2
1
3

Sample 3

Input
5
4 2
1 4
5 4
3 4
5
3 5 2
3 5 4
1 5 5
4 5 4
1 5 4
Output
5
5
5
5
5

Comments

Please read the guidelines before commenting.


There are no comments at the moment.