Background

Problem Description

Hoshino Akua gives you a tree $T(V=\{V_1,V_2,\ldots,V_n\},E)$ with edge weights $\omega: E \mapsto \mathbb{Z^+}$.

Define the weight of $S \subseteq E$ as $\omega(S)=\sum_{e \in S} \omega(e)$.

Define $R(V',E')$ to be a connected subtree of $T$ if and only if $R$ is a tree, $V' \subseteq V$, and $E' \subseteq E$.

Define the weight of $R$ as $\omega(R)=\omega(E')$.

Define the Steiner tree of $S \subseteq V$ as $f(S)=\min \{\omega(R) | S \subseteq V'\}$, where $R(V',E')$ is a connected subtree.

There are $q$ queries. In the $i$-th query, you are given $L_i, R_i, k_i$. Compute $\max \{f(S) | S \subseteq \{V_{L_i},V_{L_i+1},\ldots,V_{R_i}\},|S|=k_i\}$.

Input Format

The first line contains an integer $n$.

The next $n-1$ lines each contain three integers $a,b,z$, meaning $(V_a,V_b) \in E$ and $\omega[(V_a,V_b)]=z$. It is guaranteed that $1 \le z \le 10^9$.

The next line contains an integer $q$.

The next $q$ lines each contain three integers $L_i,R_i,k_i$. It is guaranteed that $1 \le L_i \le L_i + k_i - 1 \le R_i \le n$.

Output Format

Output $q$ lines, each containing one integer, the answer to a query.

10
1 2 2
2 3 3
3 4 2
1 5 7
2 6 7
4 7 1
1 8 3
4 9 6
7 10 4
10
5 10 5
4 9 6
10 10 1
2 6 3
6 9 3
6 9 4
7 9 2
1 3 2
1 7 3
3 8 3

35
31
0
21
23
24
16
5
22
22

Hint

Idea: nzhtl1477, Solution: rushcheyo&nzhtl1477, Code: rushcheyo, Data: rushcheyo.

This problem uses subtask grading.

Let $K=\max\{k_i\}$.

For all testdata, it is guaranteed that $1 \le n \le 3 \times 10^5$, $1 \le q \le 10^4$, and $K \le 100$.

1. $n,q \le 10$ (15 points).
2. $n,q \le 100$ (15 points).
3. $n,q \le 1000$ (10 points).
4. $n,q \le 5000$ (10 points).
5. $K=2$ (15 points).
6. $K=3$ (15 points).
7. $K \le 10$ (10 points).
8. No special constraints (10 points).

Translated by ChatGPT 5