#P18782. [2027年国家集训队互测]千层酥
[2027年国家集训队互测]千层酥
千层酥
题目描述
千层酥烘焙坊所在的小镇有 个地点,编号为1到 ,通过 条双向道路连成一棵树,每个地点均设有甜品自提柜。每条道路有正整数长度。两个地点间的距离 为树上唯一简单路径的道路长度之和。
你是烘焙坊的配送员,最初位于地点 ,需要按给定顺序配送 份千层酥。第 个订单由三个正整数 描述,客户在地点 。假设处理该订单前你位于 ,可以任意选择地点 ,前往该地点并把千层酥放入自提柜:
- 运输成本为 ;
- 顾客取货补偿为 。
处理完后你位于 ,客户取件不会改变你的位置。求处理全部订单的最小总费用。不要求最后返回地点1。答案可能超过 。
等价地,设 ,依次选择 ,最小化
$$\sum_{i=1}^m\bigl(b_i\operatorname{dist}(d_{i-1},d_i)+c_i\operatorname{dist}(d_i,a_i)\bigr).$$输入格式
第一行两个整数 。接下来 行,每行三个整数 ,表示地点 之间有一条长 的双向道路。接下来 行,每行三个整数 ,按处理顺序描述订单。
输出格式
输出一个整数,表示最小总费用。
数据范围
;每条道路满足 、、,保证这些道路组成树;每个订单满足 、。
样例
样例 1 输入
3 2
1 2 1
1 3 1
2 1 1
3 10 20
样例 1 输出
3
可以把两个订单都放在地点3。第一单运送费用1、取件费用2,第二单费用0,总费用3。
样例 2 输入
10 10
1 2 2
1 3 3
2 4 1
2 5 4
3 6 2
3 7 1
6 8 3
6 9 2
7 10 4
4 2 5
5 6 2
8 1 3
9 7 4
10 2 6
2 5 1
5 2 4
8 3 2
4 8 3
10 1 5
样例 2 输出
134
一种最优放置地点依次为2,2,6,6,10,10,2,2,2,10;各单费用9,8,16,8,14,10,36,20,3,10,合计134。
数据分组参考
下表列出数据分组性质。当前评测采用50个测试点,每点2分。
| 子任务 | n,m上限 | 特殊性质 | 分值 |
|---|---|---|---|
| 1 | 500 | 无 | 4 |
| 2 | 5000 | 7 | |
| 3 | 500000 | 所有b=1且c>=2 | 5 |
| 4 | 所有b=1 | 9 | |
| 5 | 树为链,地点1为端点 | 23 | |
| 6 | 262143 | 以地点1为根为满二叉树 | 13 |
| 7 | 200000 | 无 | 9 |
| 8 | 500000 | 10 | |
| 9 | 1000000 | 20 |