P3242 [HNOI2015] Catching Fruits

Kazami Yuuka really enjoys playing a game called osu!, and her favorite mode is catching fruits. Since she has already DT FC’d The Big Black, she thinks the game is too easy, so she invented a harder version. First, there is a map that is a tree with $n$ vertices and $n-1$ edges. There are $p$ plates on this tree. Each plate is actually a path, and each plate also has a weight. The $i$-th plate is the path from vertex $a_i$ to vertex $b_i$ (since it is a tree, the path from $a_i$ to $b_i$ is unique), with weight $c_i$. Next, $q$ fruits will fall one by one; each fruit is essentially also a path. The $i$-th fruit is the path from vertex $u_i$ to vertex $v_i$. Each time, Yuuka needs to choose one plate to catch the current fruit: a plate can catch a fruit if and only if the plate’s path is a subpath of the fruit’s path. By convention, the path from $a$ to $b$ is considered the same as the path from $b$ to $a$. To increase the difficulty, for the $i$-th fruit, among all plates that can catch it, you must choose the one with the $k_i$-th smallest weight. Each plate can be reused without limit: after catching one fruit, it can continue to catch other fruits as long as it is a subpath of the fruit’s path. Yuuka thinks this game is hard; can you solve it easily for her?

- The first line contains three integers $n$, $p$, and $q$, denoting the size of the tree, the number of plates, and the number of fruits. - The next $n-1$ lines each contain two integers $a$ and $b$, indicating that there is an edge between $a$ and $b$ in the tree. The vertices are labeled from $1$ to $n$. - The next $p$ lines each contain three integers $a$, $b$, and $c$, describing a plate whose path is from $a$ to $b$ with weight $c$, where $a \ne b$. - The next $q$ lines each contain three integers $u$, $v$, and $k$, describing a fruit whose path is from $u$ to $v$, where $u \ne v$. You need to choose the $k$-th smallest plate, and the $k$-th smallest is guaranteed to exist.

For each fruit, output one line containing the weight of the chosen plate.

For $100\%$ of the testdata, $1 \le n, p, q \le 4 \times 10^4$, $0 \le c \le 10^9$. Translated by ChatGPT 5