P12357 [eJOI 2024] 贸易搭配 / Many Pairs

EJOI 大陆由 $N$ 个城市组成，这些城市用 $1 \sim N$ 来编号。城市之间有 $N-1$ 条双向道路连接，且保证你可以从任意一个城市到达另外一个城市。换句话说，EJOI 大陆是一个树形结构。 在这个大路上还有 $K$ 个贸易关系，用城市对 $(A,B)$ 和利润 $C$ 来表示。 现在，EJOI 大陆的国王想通过以下方式测试王子的执政能力： - 首先，国王会选择一个城市 $H$ 作为首都。现在，这棵树以 $H$ 为根。 - 接下来，王子可以选择**至多两个**和 $H$ 相邻的城市。现在，$H$ 城以及以被选中城市为根的子树中的所有城市都在王子的管辖下。 选择完毕后，他的利润就等于他管辖的这些城市中的贸易关系的利润之和。**注意：当且仅当贸易关系双方都在王子管辖下，这个贸易关系的利润才可以归王子。** 现在国王还没有选好令哪个城市作为首都。但是王子很好奇，他想知道，对于每个城市，如果其作为首都，那么他可以获得的最大利润是多少。

第一行，两个正整数 $N,K$。 接下来 $N-1$ 行，每行两个整数 $U$ 和 $V$，表示大陆上的双向道路。 接下来 $K$ 行，每行三个整数 $A,B,C$，表示贸易关系。

输出一行 $N$ 个整数，第 $i$ 个表示如果让第 $i$ 个城市作为首都，那么王子可以获得的最大利润。

**【样例解释】** 以 $6$ 号城市作为首都为例，他可以选择以下城市： - $2$ 和 $3$ - $2$ 和 $4$ - $3$ 和 $4$ 其中，选择 $2$ 和 $3$ 号城市可以得到最大利润 $11+16+6=33$。 **【数据范围】** **本题采用 $\text{Subtask}$ 捆绑测试。** |$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$1$|$12$|$N,K\le50$| |$2$|$13$|$N\le5000,K\le500$| |$3$|$17$|$N\le5000,K\le2000$| |$4$|$21$|$N,K\le5000$| |$5$|$37$|无| 对于 $100\%$ 的数据： - $2 \le N,K \le 2 \times 10^5$ - $1 \le U,V,A,B \le N$ - $1 \le C \le 10^6$