درخت دودویی درختی است که هر گره آن حداکثر دو فرزند دارد. مثال زیر یک درخت دودویی با ‎۱۹‎ گره را نشان می‌دهد.

در این مثال ‎$r$‎ ریشه و طبق تعریف، گره‌های ‎$a$‎ و ‎$b$‎ به‌ترتیب سمت‌ چپ‌ترین و سمت‌ راست‌ترین نواده‌ی ‎$r$‎ هستند که آن‌ها را با ‎«سمت‌ چپ‌ترین»‎ و ‎«سمت‌ راست‌ترین»‎ گره در درخت نام می‌بریم.

به گره ‎$i$‎ یک عدد صحیح و مثبت به عنوان وزن آن نسبت می‌دهیم و آن‌را با ‎$w_i$‎ نشان می‌دهیم. هم‌چنین طول مسیر از گره ‎$i$‎ تا ریشه را عمق آن گره می‌گوییم و آن‌را با ‎$d_i$‎ نشان می‌دهیم. در مثال فوق عمق ‎$a$‎ و $b$‎ به‌ترتیب برابر ‎۲‎ و ‎۳‎ است.

وزن یک درخت را نیز برابر ‎$\sum_i w_i d_i$‎ تعریف می‌کنیم.

در این مسئله فرض کنید که وزن سمت‌ چپ‌ترین و سمت‌ راست‌ترین گره داده شده است و وزن بقیه‌ی گره‌ها برابر ‎۱‎ است. می‌خواهیم با دریافت تعداد کل گره‌ها، درختی را بیابیم که کم‌ترین وزن را داشته باشد.

• در سطر اول ورودی به‌ترتیب تعداد گره‌ها، وزن‌های سمت‌ چپ‌ترین و سمت‌ راست‌ترین گره‌ها می‌آید.
• تعداد گره‌ها حداقل ‎$3$‎ و حداکثر برابر ‎$10^{15}$‎ است.
• حداکثر وزن سمت‌ چپ‌ترین و سمت‌ راست‌ترین گره ‎$10^{10}$‎ است.
• سمت‌ چپ‌ترین و سمت‌ راست‌ترین گره نمی‌توانند ریشه درخت باشند.

در تنها سطر خروجی مقدار کم‌ترین میانگین عمق گره‌های یک درخت دودویی با ویژگی‌های داده شده را بنویسید.

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل

‎