1004. D. EERT

题目描述

给定一棵包含 (n) 个原始结点的无根树。结点 (i) 有一个整数权值 (a_i)。

你可以执行任意次以下两种操作：

1. 选择一个满足 (a_i>1) 的原始结点 (i)，支付 (x) 的代价，新建 (a_i-1) 个权值为 (1) 的结点，并将它们分别作为叶子连接到 (i)，随后令 (a_i=1)；
2. 选择两个相邻的原始结点 (i,j)，再选择一个满足 (1\le t\le a_i-1) 的整数 (t)。支付 (y) 的代价，并令

新建的叶子不能参与第二种操作。

树的直径定义为树上两点之间路径所含边数的最大值。求使最终树的直径至少为 (k) 所需的最小总代价。如果无法做到，输出 (-1)。

样例解释

第一组数据中原树直径已经为 (3)，不需要执行操作。

第二组数据中，可以花费 (3) 将结点 (1) 的一个单位权值运输到任意叶子，再花费 (7) 挂出新叶子，总代价为 (10)。

第三组数据中，将结点 (3) 的两个单位分别运输到结点 (1,5)，需要使用四条原树边。随后在两个端点各挂一次叶子，总代价为

第五组数据只有一个原始结点。一次操作可以同时挂出两个叶子，因此答案为 (11)。

数据范围

• (1\le T\le5)；
• (1\le n\le2\times10^5)；
• (1\le k\le10^9)；
• (1\le a_i\le10^9)；
• (0\le x,y\le10^9)；
• 输入的边构成一棵树。
• 所有测试数据的 (n) 之和不超过 (4\times10^5)。

输入格式

输入包含多组测试数据。第一行包含一个整数 (T)，表示测试数据组数。

对于每组测试数据：

• 第一行包含四个整数 (n,k,x,y)；
• 第二行包含 (n) 个整数 (a_1,a_2,\ldots,a_n)；
• 接下来 (n-1) 行，每行包含两个整数 (u,v)，表示原树中的一条边。

输出格式

对于每组测试数据，输出一行一个整数，表示最小总代价；如果无解，输出 (-1)。

样例输入

5
4 3 10 2
1 1 1 1
1 2
2 3
3 4
5 3 7 3
2 1 1 1 1
1 2
1 3
1 4
1 5
5 6 5 2
1 1 3 1 1
1 2
2 3
3 4
4 5
3 4 5 7
1 2 1
1 2
2 3
1 2 11 100
3

样例输出

0
10
18
-1
11

来源：2026杭电多校-测试专用（成都七中） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1232&pid=1004