挖地铁¶
参考时限：2秒；内存限制：512 MiB. 目标平台按正式文件最慢中位数的两倍、向上取整到0.5秒校准，见评测环境.
背景故事¶
工务署规划了一张树形地铁网，由 \(n\) 个地铁节点和 \(n-1\) 段铁路组成，每段铁路隧道都有一个挖掘难度。
现在，小B要去挖地铁。手工挖掘实在太慢，于是他决定用爆破来开通隧道。其中有 \(k\) 个节点可以作为爆破起始点，每个起始点都可以重复使用。一次爆破从任意一个起始点出发，到任意一个地铁节点结束，两点之间的铁路隧道便全部挖通。已经挖通的隧道可以再次经过，不会产生负面影响。
小B想知道，挖通全部隧道至少需要多少次爆破，记为 \(\mathrm{need}\)。但他未必能进行足够多次爆破，所以还想分别知道：进行 \(1,2,\ldots,\mathrm{need}\) 次爆破时，挖通隧道的挖掘难度之和最大是多少？每段隧道只计一次。
形式化问题描述¶
给定一棵有 \(n\) 个点的无向树，点编号为 \(1,\ldots,n\) . 每条边有正整数权值，其中 \(k\) 个不同的点被标记。
一次操作选择一个标记点 \(s\) 和任意点 \(t\) ，覆盖两点间唯一路径上的所有边。允许重复使用同一个标记点、同一条路径，也允许 \(s=t\) . 已覆盖的边不会重复计分。
设覆盖全部边所需的最少操作次数为 \(\mathrm{need}\) . 对每个 \(i=1,\ldots,\mathrm{need}\) ，分别求恰好进行 \(i\) 次操作时，已覆盖边的权值之和的最大值。不同的 \(i\) 可以选择完全不同的操作方案。
图中星号标记点6和7。路径 \(6\to3\) 与 \(7\to4\) 覆盖全部边，总权值为42.
输入格式¶
第一行两个整数 \(n,k\) . 第二行 \(k\) 个不同的整数，表示标记点。接下来 \(n-1\) 行，每行三个整数 \(u,v,w\) ，表示一条权值为 \(w\) 的无向边。
输出格式¶
第一行输出 \(\mathrm{need}\) . 接下来 \(\mathrm{need}\) 行，第 \(i\) 行输出恰好 \(i\) 次操作的最大覆盖权值。
样例 1¶
输入¶
4 1
1
1 2 2
2 3 2
2 4 1
输出¶
2
4
5
样例 2¶
输入¶
6 2
1 5
1 2 1
2 3 10
2 4 1
5 4 1
6 4 1
输出¶
2
12
14
样例 3¶
输入¶
6 2
1 2
1 2 3
2 3 10
2 4 1
5 4 1
6 4 1
输出¶
3
13
15
16
样例 4¶
输入¶
9 3
4 6 9
1 2 10
2 3 10
3 4 10
3 5 1
2 6 1
3 7 1
7 8 1
7 9 1
输出¶
3
30
33
35
样例 5¶
输入¶
5 1
1
1 2 2
1 3 3
1 4 4
1 5 5
输出¶
4
5
9
12
14
样例 6¶
输入¶
7 2
6 7
2 1 5
3 2 5
4 1 9
5 1 4
6 5 10
7 2 9
输出¶
2
28
42
数据范围与保证¶
\(2\le n\le1000\) , \(1\le k\le n\) , \(1\le w\le100\) . 输入保证是一棵树，标记点互不相同。
本题经授权重新设计：点数上限调整为1000，采用精确算法；覆盖规则、两项输出目标及边权范围保持一致。规格整理与参考实现：Codex（GPT-6）。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |
共10个正式文件，每个10%。生成说明。