#P18782. [2027年国家集训队互测]千层酥

[2027年国家集训队互测]千层酥

千层酥

题目描述

千层酥烘焙坊所在的小镇有 nn 个地点,编号为1到 nn,通过 n−1n-1 条双向道路连成一棵树,每个地点均设有甜品自提柜。每条道路有正整数长度。两个地点间的距离 dist⁡(u,v)\operatorname{dist}(u,v) 为树上唯一简单路径的道路长度之和。

你是烘焙坊的配送员,最初位于地点 11,需要按给定顺序配送 mm 份千层酥。第 ii 个订单由三个正整数 ai,bi,cia_i,b_i,c_i 描述,客户在地点 aia_i。假设处理该订单前你位于 yy,可以任意选择地点 xx,前往该地点并把千层酥放入自提柜:

  • 运输成本为 bidist⁡(y,x)b_i\operatorname{dist}(y,x);
  • 顾客取货补偿为 cidist⁡(x,ai)c_i\operatorname{dist}(x,a_i)。

处理完后你位于 xx,客户取件不会改变你的位置。求处理全部订单的最小总费用。不要求最后返回地点1。答案可能超过 101910^{19}。

等价地,设 d0=1d_0=1,依次选择 d1,…,dm∈{1,…,n}d_1,\ldots,d_m\in\{1,\ldots,n\},最小化

$$\sum_{i=1}^m\bigl(b_i\operatorname{dist}(d_{i-1},d_i)+c_i\operatorname{dist}(d_i,a_i)\bigr).$$

输入格式

第一行两个整数 n,mn,m。接下来 n−1n-1 行,每行三个整数 u,v,wu,v,w,表示地点 u,vu,v 之间有一条长 ww 的双向道路。接下来 mm 行,每行三个整数 ai,bi,cia_i,b_i,c_i,按处理顺序描述订单。

输出格式

输出一个整数,表示最小总费用。

数据范围

1≤n,m≤1061\le n,m\le10^6;每条道路满足 1≤u,v≤n1\le u,v\le n、u≠vu\ne v、1≤w≤1091\le w\le10^9,保证这些道路组成树;每个订单满足 1≤ai≤n1\le a_i\le n、1≤bi,ci≤1091\le b_i,c_i\le10^9。

样例

样例 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

样例附件