智乃的QTree Problem

题号：NC288757
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

给定一颗尺寸大小为 $n$ 的树 $T(V,E)$ ，每个节点有一颗权值 $a_i$ ，现在定义 $Path(s,t)$ 表示一条从 $s$ 到 $t$ 的简单路径， $Val(s,t)$ 表示这条简单路径上的 $a_i$ 的极值差。

现在给定一个查询参数 $l$ ，智乃想知道所有满足 $|a_s-a_t|\leq l$ 简单路径 $Val(s,t)$ 之和是多少？

假定路径有向，你需要对 $Val(s,t)$ 和 $Val(t,s)$ 分别统计一次结果。

形式化的：

定义 $T(V,E)$ 表示一个顶点集合为 $V$ ，边集合为 $E$ ，大小为 $n$ 的无根树

定义 $Path(s,t)=\{v_0,v_1,v_2,...,v_{k-1}\},s=v_0,t=v_{k-1},v_i\in V,(v_i,v_{i+1})\in E$ 。

定义 $Val(s,t)=max_{u,v\in Path(s,t)}\{a_u-a_v\}$ 。

给定一个查询参数 $l$ ，求 $\sum\limits ^{n}_{i=1}\sum\limits ^{n}_{j=1}Val(i,j)\cdot [|a_i-a_j|\leq l]$ 。

输入描述:

第一行输入两个正整数，表示树的尺寸，查询参数

接下来一行输入个非负整数，表示权值数组

接下来行，输入树结构，每行两个正整数表示树上的一条边

输出描述:

输出一个整数表示问题的答案

示例1

输入

复制

输出

复制

示例2

输入

复制

输出

复制