#P16035. [Oni2024]Arbore

[Oni2024]Arbore

题目描述

给定一棵有 NN 个节点的树,节点编号为 11 到 NN。每条边都有一个非零自然数作为费用。

一次操作定义为:选择一条当前费用严格大于 00 的边,并将这条边的费用减少 11。

对于树上的一个节点 vv 和一个自然数 kk,定义 f(v,k)f(v,k) 为:在最多进行 kk 次上述操作后,从节点 vv 到树中所有其他节点的路径费用之和的最小可能值。

也就是说,可以在整棵树上任选边进行至多 kk 次减费操作,使得以 vv 为起点到所有其他节点的距离总和尽可能小。

任务

给定 QQ 个询问,每个询问形如 (v,k1,k2)(v,k_1,k_2),其中 vv 是树上的一个节点,且 k1≤k2k_1\le k_2。

对于每个询问,计算

∑k=k1k2f(v,k)\sum_{k=k_1}^{k_2} f(v,k)

并输出结果对 109+710^9+7 取模后的值。

输入格式

第一行包含整数 NN,表示树的节点数。

接下来 N−1N-1 行,每行包含三个整数 u,v,wu,v,w,表示节点 uu 与节点 vv 之间有一条费用为 ww 的边。

接下来一行包含整数 QQ,表示询问数。

接下来 QQ 行,每行包含三个整数 v,k1,k2v,k_1,k_2,表示一个询问。

输出格式

输出 QQ 行。每行输出对应询问的答案,按输入顺序排列。

数据范围

  • 2≤N≤2000002\le N\le 200000
  • 1≤Q≤4000001\le Q\le 400000
  • 1≤w≤1081\le w\le 10^8
  • 0≤k1≤k2≤10140\le k_1\le k_2\le 10^{14}

子任务

子任务 分值 限制
1 12 N≤2000, Q≤2000, k1=k2=0N\le 2000,\ Q\le 2000,\ k_1=k_2=0
2 7 N≤200000, Q≤400000, k1=k2=0N\le 200000,\ Q\le 400000,\ k_1=k_2=0
3 13 N≤2000, Q≤2000, k1=k2N\le 2000,\ Q\le 2000,\ k_1=k_2
4 16 N≤5000, Q≤200000, k1=k2N\le 5000,\ Q\le 200000,\ k_1=k_2
5 19 N≤100000, Q≤100000, k1=k2N\le 100000,\ Q\le 100000,\ k_1=k_2
6 14 N≤200000, Q≤400000, k1=k2N\le 200000,\ Q\le 400000,\ k_1=k_2
7 11 N≤100000, Q≤100000N\le 100000,\ Q\le 100000
8 无额外限制

样例

输入

5
1 2 3
2 3 4
2 5 6
1 4 2
4
1 4 5
2 1 1
5 20 22
4 0 0

输出

21
16
0
27

样例解释

样例中的树有 N=5N=5 个节点,边权如图所示,共有 Q=4Q=4 个询问。

第一个询问中:

  • 当 k=4k=4 时,可以将边 1−21-2 减少 33 次,将边 1−41-4 减少 11 次,得到 f(1,4)=11f(1,4)=11;
  • 当 k=5k=5 时,可以将边 1−21-2 减少 33 次,将边 2−32-3 减少 11 次,将边 2−52-5 减少 11 次,得到 f(1,5)=10f(1,5)=10。

因此第一个询问的答案为 f(1,4)+f(1,5)=21f(1,4)+f(1,5)=21。

第二个询问中,将边 1−21-2 减少 11 次,可以得到 f(2,1)=16f(2,1)=16。

第三个询问中,对于 20≤k≤2220\le k\le 22 的所有 kk,所有边权都可以被减少到 00,因此答案为 00。

第四个询问中,k1=k2=0k_1=k_2=0,没有任何操作可用。从节点 44 到其他节点的路径费用之和为 2+5+9+11=272+5+9+11=27。