#2000. 千层酥

    ID: 2000 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest4621来源:qoj.ac数据:公开样例贪心

千层酥

千层酥

题目描述

标题: 千层酥 - Problem - QOJ.ac

IOI 2027 中国国家集训队互测 Day 5

C. 千层酥

Statistics

题目描述

千层酥烘焙坊所在的小镇有 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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 2
1 2 1
1 3 1
2 1 1
3 10 20
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
134