Cây khung Hamilton

Có $n$ thành phố. Giữa mỗi cặp thành phố đều có một con đường hai chiều, nên tổng cộng có $\frac{n(n-1)}{2}$ con đường.

Ban đầu, đi qua mỗi con đường mất đúng $y$ giây. Sau đó, người ta chọn ra một cây khung của mạng lưới, tức là một tập hợp gồm $n-1$ con đường sao cho từ thành phố bất kỳ có thể đi tới mọi thành phố khác chỉ bằng các con đường trong tập này. Với mỗi con đường thuộc cây khung, thời gian đi qua nó được đổi từ $y$ thành $x$ giây (lưu ý $x$ không nhất thiết nhỏ hơn $y$).

Bạn muốn đi thăm tất cả các thành phố sao cho tổng thời gian là nhỏ nhất. Hành trình bắt đầu ở một thành phố bất kỳ, kết thúc ở một thành phố bất kỳ, và mỗi thành phố được thăm đúng một lần. Hãy tìm tổng thời gian nhỏ nhất của một hành trình như vậy.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $x$, $y$.
• $n-1$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $u_i$ và $v_i$ là hai thành phố được nối bởi con đường thứ $i$ của cây khung.

Dữ liệu đảm bảo các con đường này tạo thành một cây khung.

Dữ liệu ra

In ra một số nguyên duy nhất: tổng thời gian nhỏ nhất cần bỏ ra để thăm tất cả các thành phố, mỗi thành phố đúng một lần.

Ràng buộc

• $2\le n\le 200000$
• $1\le x,y\le {10}^9$

Ví dụ