一组 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$$。