CF618D Hamiltonian Spanning Tree

n 个城市之间形成了一个有n*(n-1)/2条边的完全无向图。走每条边需要y秒。 给定该图的一个n-1条边的生成树，走树上的每一条边只需要x秒（不过注意x不一定小于y）。 你希望从任意一个点开始，经过每个点恰好一次，在任意一个点结束的路径的长度所花时间最少。求最少时间。

无

无

In the first sample, roads of the spanning tree have cost $ 2 $ , while other roads have cost $ 3 $ . One example of an optimal path is . In the second sample, we have the same spanning tree, but roads in the spanning tree cost 3, while other roads cost 2. One example of an optimal path is .