P12462 [Ynoi Easy Round 2018] 星野爱久爱海


星野阿库娅给了你一棵树 $T(V=\{V_1,V_2,\ldots,V_n\},E)$，树有边权 $\omega: E \mapsto \mathbb{Z^+}$。 定义 $S \subseteq E$ 的权值为 $\omega(S)=\sum_{e \in S} \omega(e)$。 定义 $R(V',E')$ 是 $T$ 的 $\textbf{连通子树}$，当且仅当 $R$ 是树，$V' \subseteq V$，$E' \subseteq E$。 定义 $R$ 的权值 $\omega(R)=\omega(E')$。 定义 $S \subseteq V$ 的 Steiner 树为 $f(S)=\min \{\omega(R) | S \subseteq V'\}$，其中 $R(V',E')$ 是连通子树。 有 $q$ 次询问，第 $i$ 次给出 $L_i,R_i,k_i$，求 $\max \{f(S) | S \subseteq \{V_{L_i},V_{L_{i}+1},\ldots,V_{R_i}\},|S|=k_i\}$。

无

无

Idea：nzhtl1477，Solution：rushcheyo&nzhtl1477，Code：rushcheyo，Data：rushcheyo 本题采用子任务评测。 设 $K=\max\{k_i\}$。 对所有数据，保证 $1 \le n \le 3 \times 10^5,1 \le q \le 10^4,K \le 100$. 1. $n,q \le 10$（15 分）； 2. $n,q \le 100$（15 分）； 3. $n,q \le 1000$（10 分）； 4. $n,q \le 5000$（10 分）； 5. $K=2$（15 分）； 6. $K=3$（15 分）； 7. $K \le 10$（10 分）； 8. 没有特殊性质（10 分）。