26602번 - 인생은 B와 D 사이의 C다.

아욱은 트리 나라에 사는 정점의 개수가 $N$이고 $1$번 정점을 루트로 하는 트리다. 지난 21년간 운동은 하나도 안 하고 먹기만 한 아욱의 정점은 모두 지방으로 이루어져 있다. 프링글스를 먹으며 인터넷을 탐방하던 아욱은 어느 날 다음과 같은 명언을 발견했다.

"인생은 Bulk up과 Diet 사이의 Choice다."

명언을 보고 감명받은 아욱은 프링글스를 쓰레기통에 쏟아붓고 바로 헬스장으로 뛰어갔다! 하지만 헬스 트레이너 선생님께서는 아욱의 몸을 보고선 고개를 절레절레 흔들며 이렇게 말했다.

"이 정도 몸이면... 벌크업 한 번 할 때 $b$ 일, 다이어트 한 번 할 때 $d$ 일 걸리겠는데요?”

트리 나라에 사는 누구나 다 아는 사실이지만 벌크업을 한 번 하면 말단 정점에 근육 정점 하나를 붙일 수 있다. 또한 다이어트를 한 번 하면 자신의 몸에 있는 말단 지방 정점을 하나 제거할 수 있다.

아욱은 잠시 의지가 꺾일 뻔했으나 금세 마음을 고쳐먹고 트리 나라의 미의 기준인 포화 이진 트리의 형태가 되기 위해 헬스장에 등록하기로 했다! 하지만 아욱은 가난한 대학생이라 헬스장 등록으로 빠지는 지출을 무시할 수 없다. 따라서 아욱은 최대한 짧은 기간만 헬스장에 다녀 포화 이진 트리의 형태가 되기로 결심했다.

인바디를 재고 있어 움직일 수 없는 아욱을 대신해 아욱이 포화 이진 트리의 형태가 될 수 있는 가장 짧은 헬스장 등록 기간을 구해주도록 하자.

첫째 줄에 아욱의 정점의 개수 $N$, 벌크업 한 번할 때 걸리는 기간 $b$, 다이어트 한 번할 때 걸리는 기간 $d$가 사이에 공백을 두고 주어진다. $\left(1 \leq N, b,d \leq 111\,222 \right)$

다음 $N-1$개의 줄에 걸쳐, 줄마다 아욱의 간선이 u v와 같은 형식으로 주어진다. $\left(1 \leq u, v \leq N \right)$

이는 아욱의 $u$번 정점과 $v$번 정점이 서로 연결되어 있음을 의미한다. 주어지는 입력은 모두 정수다.

첫째 줄에 아욱이 포화 이진 트리의 형태가 될 수 있는 가장 짧은 헬스장 등록 기간을 출력한다.

포화 이진 트리는 말단 정점이 아닌 모든 정점이 두 개의 자식 정점을 갖고, 모든 말단 정점이 동일한 깊이를 갖는 트리를 말한다.