CF2014F Sheriff's Defense

给定一张 $n$ 结点 $n - 1$ 条边的有点权的树。初始每个结点都是黑色。 你可以执行任意次以下操作：将一个黑点染成白色，并将所有与它相邻的结点的权值减去 $c$（不包括自己）。 最大化全部白点的权值之和。

多组数据。 第一行一个整数 $t\ (1 \le t \le 10 ^ 4)$，表示数据组数。 对于每组数据：第一行两个整数 $n$，$c\ (1 \le n \le 2 \cdot 10 ^ 5, 1 \le c \le 10 ^ 9)$，含义如题面所述。接下来 $n$ 个数，第 $i$ 个数表示结点 $i$ 的点权 $a_i$。接下来 $n - 1$ 行，每行两个整数 $u$，$v\ (1 \le u, v \le n, u \ne v)$，表示有一条 $u \to v$ 的边。 保证 $\sum n \le 2 \cdot 10 ^ 5$。

输出 $t$ 行，表示最大的全部白点的权值之和。 Translated by liuli688

In the first test case, it is optimal to strengthen the second base. The final gold at each base is $ [1,3,0] $ . In the second test case, it is optimal to strengthen all bases. The final gold at each base is $ [2,4,2] $ . In the third test case, it is optimal to not strengthen any base.