فهرست مندرجات
Tree
درخت دودویی درختی است که هر گره آن حداکثر دو فرزند دارد. مثال زیر یک درخت دودویی با ۱۹ گره را نشان می‌دهد.
در این مثال $r$ ریشه و طبق تعریف، گره‌های $a$ و $b$ به‌ترتیب سمت چپ‌ترین و سمت راست‌ترین نواده‌ی $r$ هستند
که آن‌ها را با «سمت چپ‌ترین» و «سمت راست‌ترین» گره در درخت نام می‌بریم.
به گره $i$ یک عدد صحیح و مثبت به عنوان وزن آن نسبت می‌دهیم و آن‌را با $w_i$ نشان می‌دهیم. هم‌چنین طول مسیر از گره $i$ تا ریشه را عمق آن گره می‌گوییم و آن‌را با $d_i$ نشان می‌دهیم. در مثال فوق عمق $a$ و $b$ به‌ترتیب برابر ۲ و ۳ است.
وزن یک درخت را نیز برابر $\sum_i w_i d_i$ تعریف می‌کنیم.
در این مسئله فرض کنید که وزن سمت چپ‌ترین و سمت راست‌ترین گره داده شده است و وزن بقیه‌ی گره‌ها برابر ۱ است. می‌خواهیم با دریافت تعداد کل گره‌ها، درختی را بیابیم که کم‌ترین وزن را داشته باشد.
ورودی
- در سطر اول ورودی به‌ترتیب تعداد گره‌ها، وزن‌های سمت چپ‌ترین و سمت راست‌ترین گره‌ها می‌آید.
- تعداد گره‌ها حداقل $3$ و حداکثر برابر $10^{15}$ است.
- حداکثر وزن سمت چپ‌ترین و سمت راست‌ترین گره $10^{10}$ است.
- سمت چپ‌ترین و سمت راست‌ترین گره نمی‌توانند ریشه درخت باشند.
خروجی
در تنها سطر خروجی مقدار کم‌ترین میانگین عمق گره‌های یک درخت دودویی با ویژگی‌های داده شده را بنویسید.
محدودیت‌ها
- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت