[SGU547] Divide The Kingdom

题目描述

Berland 王国有 $n$ 座城市，由 $n-1$ 条双向道路连接，任意两座城市之间都可以互相到达，因此整个道路网络是一棵树。

国王和王后决定分开生活。他们分别要选择一组非空城市作为自己的领地，剩余城市全部被摧毁。摧毁第 $i$ 座城市的费用为 $p_i$。

国王选择的城市集合必须满足：

1. 该集合在原树中连通；
2. 与王后的城市集合没有公共城市；
3. 国王领地中的任何城市都不能与王后领地中的城市通过一条道路直接相连；
4. 国王领地内部任意两座城市之间距离的最大值恰好为 $D_1$；
5. 考虑所有距离恰好等于 $D_1$ 的城市对，把这些城市对中出现过的不同端点全部取出，其数量不能超过 $C_1$。若领地中只有一座城市，则这样的城市对数量为 $0$。

王后的要求完全相同，只是对应参数为 $D_2,C_2$。

所有既不属于国王也不属于王后的城市都必须被摧毁，同时与它们相连的道路也被删除。

请判断是否能满足两人的要求。如果可以，求摧毁城市的最小总费用。

树上两点间的距离定义为它们之间简单路径所经过的道路数。

输入格式

第一行包含整数 $n$，其中 $3\le n\le200$。

第二行包含四个整数 $D_1,C_1,D_2,C_2$，满足 $0\le D_1,D_2\le n-1$，$1\le C_1,C_2\le n$。

第三行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$，其中 $1\le p_i\le1000$，表示摧毁各城市的费用。

接下来 $n-1$ 行，每行两个整数 $a_j,b_j$，表示一条连接城市 $a_j$ 和 $b_j$ 的道路。

输出格式

如果不存在合法方案，输出一行：

-1

否则，输出一行一个整数，表示摧毁城市的最小总费用。

样例 1

样例输入

10
4 2 0 1
5 2 5 2 5 5 5 5 5 2
1 4
6 1
1 2
7 1
3 7
10 7
9 10
7 8
8 5

样例输出

6

样例 2

样例输入

4
1 2 1 2
9 9 9 9
1 2
2 3
3 4

样例输出

-1