题目描述
给定⼀个 $n$ 个点的带边权的树和⻓度为 $n - 1$ 的数组 $f$ 。对于⼀个 $01$ 字符串 $s$，考虑它有 $m$ 段 $1$，每段的⻓度为 $l_i$，那么字符串 $s$ 的权值为 $\sum_{i=1}^mf_{l_i}$。有 $q$ 次询问，每次询问给定 $3$ 个数 $u,v,w(u \neq v)$，我们把树上边权 $\geq w$ 的边视作 $1$，否则视作 $0$，把 $u$ 到 $v$ 路径上的边上的字符顺次连起来形成⼀个字符串，求这个字符串的权值。
输入格式
第一行两个正整数 $n,q$。
第二行 $n - 1$ 个整数表示序列 $f$。
接下来 $n - 1$ 行，每行 $3$ 个正整数 $u,v,w$，表示一条树边。
接下来 $q$ 行，每行三个正整数 $u,v,w(u \neq v)$，表示一个询问。
输出格式
共 $q$ 行，第 $i$ 行表示第 $i$ 个询问的答案。
样例 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其余样例⻅下发⽂件。
数据范围和提⽰
对于全部的数据，$2 \leq n \leq 10^5,1 \leq q \leq 10^5,|f_i| \leq 1000,1 \leq u,v \leq n,1 \leq w \leq 10^9$ 。
- $\textbf{Subtask 1(20pts)}$ : $n,q \leq 1000$
- $\textbf{Subtask 2(20pts)}$ : 保证树随机⽣成，⽣成⽅式为对 $i \in [2,n]$ 随机⼀个范围在 $[1,i - 1]$ 的⽗亲。
- $\textbf{Subtask 3(20pts)}$ : $i \in [2,n]$ 号点的父亲为 $i - 1$。
- $\textbf{Subtask 4(40pts)}$ : 无特殊限制。