#P6694. [2019山东省队集训第一轮]喜欢最最痛

    ID: 6544 传统题 2000ms 512MiB 尝试: 30 已通过: 3 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS图论欧拉回路构造与建模奇偶性分析贪心反悔贪心树算法树链剖分动态规划动态 DP数据结构懒标记线段树有序多重集合排序与序列处理离散化树状数组倍增求第 k 小二分查找数值计算与优化凸性/单峰性判定CF3200

[2019山东省队集训第一轮]喜欢最最痛

[2019山东省队集训第一轮]喜欢最最痛

题目背景

分开了哦算,

自身的成功。

喜欢最最痛,

最成功租房。

——龚诗锋《么片对棠》

题目描述

给定一棵有 nn 个结点的带权树,所有边权均为正整数。

你需要从结点 11 出发,经过所有原树边至少一次,最终回到结点 11。允许重复经过边,每次经过的边权都计入总成本。

你可以按顺序添加额外的无向边,第 ii 条添加的边权为 AiA_i,它的两个端点可以自行选择。最终的行走路线不必经过所有已添加的额外边。

对于每个 K=0,1,…,mK=0,1,\ldots,m,求最多允许添加 KK 条额外边时的最小行走成本。

由于添加后可以不使用,允许添加 KK 条等价于拥有前 KK 个权值 A1,…,AKA_1,\ldots,A_K 对应的额外边,并可只使用其中一部分。不同的 KK 分别求解。

输入格式

第一行两个正整数 n,mn,m。

接下来 n−1n-1 行,每行三个整数 u,v,wu,v,w,表示原树中一条连接 u,vu,v、权值为 ww 的无向边。

接下来一行 mm 个正整数 A1,A2,…,AmA_1,A_2,\ldots,A_m。

输出格式

输出 m+1m+1 个整数。第 K+1K+1 个数表示最多允许添加 KK 条额外边时的最小成本,其中 0≤K≤m0\le K\le m。

样例输入

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

样例输出

50 37 34 34 29 29

其他样例

原题样例 2 见选手目录下的 love/love2.in 和 love/love2.ans,其范围符合子任务 2。

原题样例 3 见选手目录下的 love/love3.in 和 love/love3.ans,其范围符合子任务 4。

数据范围

所有数据满足 2≤m≤n≤1052\le m\le n\le10^5,1≤Ai,w≤1091\le A_i,w\le10^9。

子任务 分值 nn 的上界 mm 的上界 特殊性质
1 10 分 1010 无
2 20 分 30003000
3 10 分 10510^5 22
4 5 分 10510^5 所有原树边均有一个端点为 11
5 55 分 无