#PQJ4621x21440. QOJ 4621_21440
QOJ 4621_21440
标题: 千层酥 - Problem - QOJ.ac
IOI 2027 中国国家集训队互测 Day 5
C. 千层酥
题目描述
千层酥烘焙坊所在的小镇有 n 个地点,编号从 1 到 n,由 n−1 条双向道路连接成一棵树。每条道路都有一个正整数长度,每个地点都设有一个甜品自提柜。定义 dis(u,v) 为地点 u 到地点 v 的简单路径上所有道路的长度之和。
你是烘焙坊的配送员,初始位于地点 1,需要按顺序配送 m 份千层酥。第 i 份订单的顾客住在地点 ai,这份订单的单位运输成本为 bi,单位取货补偿为 ci。
配送第 i 份订单时,假设你当前位于地点 y,你可以任选一个地点 x,前往该地点并将千层酥放入自提柜。本次配送需要支付:
- 运输成本 dis(y,x)⋅bi;
- 顾客取货的补偿 dis(x,ai)⋅ci。
完成这份订单后,你位于地点 x,并从这里继续配送下一份订单。顾客取货不会影响后续配送。
请你安排每份订单的存放地点,使全部订单的运输成本与取货补偿之和最小。完成全部订单后,你不需要返回起点。
形式化地,设 di 为第 i 份订单的存放地点,令 d0=1,你需要最小化:
∑i=1m(dis(di−1,di)⋅bi+dis(di,ai)⋅ci).
请注意,在本题的数据范围下,答案可能超过 1019。
输入格式
第一行包含两个整数 n,m,分别表示地点数量和订单数量。
接下来 n−1 行,每行包含三个整数 u,v,w,表示地点 u,v 之间有一条长度为 w 的双向道路。
接下来 m 行,第 i 行包含三个整数 ai,bi,ci,分别表示第 i 份订单的顾客所在地、单位运输成本和单位取货补偿。
输出格式
输出一行一个整数,表示最小总代价。
样例 1 输入
3 2
1 2 1
1 3 1
2 1 1
3 10 20
样例 1 输出
3
样例 1 说明
一种最优方案是将两份千层酥都放在地点 3 的自提柜中。
配送第一份订单时,从地点 1 前往地点 3,运输成本为 1,取货补偿为 2,本次代价为 3。配送第二份订单时留在地点 3,本次代价为 0。
样例 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,2,6,6,10,10,2,2,2,10。
各次配送的代价依次为 9,8,16,8,14,10,36,20,3,10,总代价为 134。
数据范围
对于所有测试数据:
- 1≤n,m≤106;
- 1≤u,v,ai≤n,u≠v;
- 1≤w,bi,ci≤109;
- 输入的 n−1 条道路构成一棵树。
本题采用子任务捆绑评分,通过一个子任务的所有测试点才能获得该子任务的分数。同时开启了合理的子任务依赖。
子任务编号 n,m≤ 特殊性质 分数 1 500 无 4 2 5000 无 7 3 5×105 bi=1,ci≥2 5 4 5×105 bi=1 9 5 5×105 树的形态是以 1 为端点的链 23 6 262143 树的形态是以 1 为根的满二叉树 13 7 2×105 无 9 8 5×105 无 10 9 106 无 20