← 返回题目列表

Codeforces · 618/D

D. 哈密顿生成树

中文机器翻译题面 查看原题

一组 n 个城市通过道路网络连接起来。每对城市之间都有一条无向道路,因此总共有 $$\frac{n \cdot (n-1)}{2}$$ 条道路。穿过任何一条道路都需要 y 秒。

生成树是一组恰好包含 n - 1 条道路的道路,这样就可以仅使用这些道路在任意两个城市之间行驶。

选择了初始网络的一些生成树。对于这棵树中的每条道路,穿过这条道路所需的时间从 y 秒更改为 x 秒。请注意,不能保证 x 小于 y。

您想使用尽可能最短的路径穿越所有城市。给定 n、x、y 和所选生成树的描述,求从任何城市开始、到任何城市结束并恰好访问所有城市一次的最短路径的成本。

输入

输入的第一行包含三个整数 n、x 和 y (2 ≤ n ≤ 200 000, 1 ≤ x, y ≤ 109)。

接下来的 n - 1 行中的每一行都包含生成树中道路的描述。这些行的第 i 行包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n)——第 i 条道路连接的城市的索引。保证这些道路形成一棵生成树。

输出

打印一个整数 - 访问所有城市一次所需花费的最少秒数。

示例

输入 #1

5 2 3
1 2
1 3
3 4
5 3

输出 #1

9

输入 #2

5 3 2
1 2
1 3
3 4
5 3

输出 #2

8

注意

在第一个样本中,生成树的道路的成本为 2,而其他道路的成本为 3。最佳路径的一个示例是 $$5 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 2$$。

在第二个示例中,我们有相同的生成树,但生成树中的道路成本为 3,而其他道路成本为 2。最佳路径的一个示例是 $$1\rightarrow4\rightarrow5\rightarrow2\rightarrow3$$。