P12462 [Ynoi Easy Round 2018] Hoshino Ai Kuu Ai Mi


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\}$.

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 $q$ lines, each containing one integer, the answer to a query.

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