徐老师的施肥计划
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
夏天到了，在这么热的天气里吃上一块冰镇西瓜，多是一件美事啊！
于是在自己家花园里开辟了一块土地用来种西瓜，为了快速吃到西瓜，徐老师只是简单的挖了 $n$ 个坑（编号 $1 \sim n$）用来种西瓜，西瓜坑和西瓜坑之间也只铺了 $n-1$ 条小路来连接它们
而因为这些小路是徐老师简单挖出来的，所以每条小路有一个易坏度 $a_i$，一开始每条路的损坏程度是 $0$，每当有人或者机器经过这条小路，这条路的损坏程度就会增加 $a_i$
聪明的徐老师为了方便施肥，特意造了一台施肥机，将地图的信息输入到了施肥机中后，设计了一系列施肥方案：每个方案由 $u_i,v_i,r_i$ 描述，表示施肥机会由 $u_i$ 出发，沿着小路到达 $v_i$
而施肥机每次会带上一定重量的肥料，可能会对小路造成更多的破坏，这里用 $r_i$ 来表示这一次施肥机对小路破坏程度增加的系数，也就是原本经过一条小路时，会让小路的损坏程度增加 $a_x$，现在变成 $a_x * r_i$
现在徐老师在施肥机进行施肥方案的过程中，会进行西瓜地的损坏程度查询
设 $len_{i,j}$ 表示西瓜坑 $i$ 到西瓜坑 $j$ 的路径上所有小路的损坏程度之和
整个西瓜地的损坏程度即为 $\sum{len_{i,j}},其中 1 \leq i,j \leq n$
输入格式
输入一个整数 $n$ 表示西瓜坑的数量接下来 $n - 1$ 行，每行三个整数 $x_i,y_i,a_i$ 表示编号为 $x_i,y_i$ 的西瓜坑之间存在一条小路，这条小路的易坏度为 $a_i$
为了方便，这里将施肥方案和查询合并为 $m$ 次操作
对于第 $i$ 次操作，首先一个整数 $op$ 用来描述这是施肥方案还是查询
$op == 1$ 时表示这是一个施肥方案，接下来输入三个整数 $u_i,v_i,r_i$，含义如题，并且施肥机会执行这个施肥方案
$op == 2$ 时表示这是徐老师的一次查询，请计算整个西瓜地现在的损坏程度
| 测试点编号 | $n,m \leq$ | 特殊性质 |
| :---: | :---: | :---: |
| 1 | 10 | 树是一条链 |
| 2 | 1000 | 树是一条链 |
| 3 | $10^5$ | 树是一条链 |
| 4-5 | 200 | 无 |
| 6-7 | 2000 | 无 |
| 8-10 | $2*10^5$ | 无 |
输出格式
因为查询次数可能很多，为了方便，请将每次查询的结果求和，并对 $10^9+7$ 取模输出
样例
3
1 2 10
2 3 1
3
2
1 1 3 3
266提示
第一次查询的结果为 $0$接下来一个施肥方案从 $1$ 到 $3$，会经过 $1$ 号边和 $2$ 号边，$1$ 号边的损坏程度增加 $10 * 3 = 30$， $2$ 号边的损坏程度增加 $1 * 3 = 3$
此时 $1$ 号边的损坏程度为 $30$, $2$ 号边的损坏程度为 $3$
第二次查询的结果为 $len_{1,2} + len_{2,3} + len{1,3} = 30 + 3 + 33 = 66$
最后答案即为 $0 + 66 = 66$
2023暑CSP-S复赛集训模拟赛三
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-7-30 22:15
- 结束于
- 2023-8-9 22:15
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 22
