← 返回题目列表

Codeforces · 536/E

E. 路上的塔瓦斯

中文机器翻译题面 查看原题

塔瓦斯住在塔瓦斯波利斯。塔瓦斯波利斯有 n 个城市,编号从 1 到 n,由 n - 1 条双向道路连接。任意两个城市之间都存在一条路径。每条路也都有长度。

Tavas 最喜欢的字符串是二进制字符串(它们只包含 0 和 1)。对于任何二进制字符串,如 s = s1s2...sk,T(s) 就是它的优点。 T(s) 可以计算如下:

考虑该字符串中正好有 m 个 1 块(s 中的 1 块是 s 中仅包含 1 的最大连续子串),长度为 x1, x2, ..., xm。

定义 $$T(s) = \sum_{i=1}^{m} f_{x_i}$$ 其中 f 是给定序列(如果 m = 0,则 T(s) = 0)。

Tavas 喜欢查询。他要求你回答 q 个问题。在每个查询中,他都会给你数字 v、u、l,你应该打印以下数字:

考虑从城市 v 到城市 u 的道路:e1,e2,...,例如。

构建长度为 x 的二进制字符串 b,使得:bi = 1 当且仅当 l ≤ w(ei) 其中 w(e) 是道路 e 的长度。

您应该为此查询打印 T(b)。

输入

输入的第一行包含整数 n 和 q(2 ≤ n ≤ 105 且 1 ≤ q ≤ 105)。

下一行包含 n - 1 个空格分隔的整数 f1, f2, ..., fn - 1 (|fi| ≤ 1000)。

接下来的 n - 1 行包含道路的详细信息。每行包含整数 v、u 和 w,这意味着城市 v 和 u 之间有一条长度为 w 的道路(1 ≤ v,u ≤ n 且 1 ≤ w ≤ 109)。

接下来的 q 行包含查询的详细信息。每行包含整数 v、u、l(1 ≤ v、u ≤ n、v ≠ u 且 1 ≤ l ≤ 109)。

输出

在一行中打印每个查询的答案。

示例

输入 #1

2 3
10
1 2 3
1 2 2
1 2 3
1 2 4

输出 #1

10
10
0

输入 #2

6 6
-5 0 0 2 10
1 2 1
2 3 2
3 4 5
4 5 1
5 6 5
1 6 1
1 6 2
1 6 5
3 6 5
4 6 4
1 4 2

输出 #2

10
-5
-10
-10
-5
0