Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB
Statistics

题目描述

给定⼀个 $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)}$ : 无特殊限制。

下发文件