时空限制

1S/512M

题目描述

给定一棵包含 $n$ 个节点的有根树，根节点为 $1$，根节点的深度定义为 $1$。每个节点 $i$ 有一个权值 $w_i$，以及两个长度为 $n$ 的约束数组 $a$ 和 $b$。

你需要选择至多 $k$ 条互不相交的链，满足以下条件：

• 每条链的两个端点必须具有祖先-后代关系（即其中一个节点是另一个节点的祖先）。

• 以深度为 $i$ 的节点作为链的上端点（深度较小的一端）的链的数量不超过 $b_i$。

• 以深度为 $i$ 的节点作为链的下端点（深度较大的一端）的链的数量不超过 $a_i$。

你的目标是最大化所有被选中的链覆盖的节点的权值之和。

格式

输入格式

第一行包含两个正整数 $n$ 和 $k$。

第一行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，代表下端点深度限制。

第二行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，代表上端点深度限制。

第三行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$，代表每个节点的权值。

接下来 $n-1$ 行，每行包含两个整数 $u, v$，表示 $u$ 和 $v$ 之间有 $1$ 条边。

输出格式

输出一个整数，表示在满足所有约束条件下，被链覆盖的点的最大权值总和。

样例

样例输入 #1

5 2
5 5 5 5 5
1 5 5 5 5
10 2 8 3 7
1 2
2 3
3 4
4 5

样例输出 #1

30

数据规模

对于 $20\%$ 的数据， $w_i$ 均相同。

对于 $100\%$ 的数据，$1 \leq n , k, a_i, b_i \leq 300$，$1 \leq w_i \leq 10^9$。