+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- آقای پنگ، رئیس کل زندان اوین است. در این زندان $n$ خلاف‌کار در بند هستند و از $1$ تا $n$ شماره‌گذاری شده‌اند. میزان ارتباط دو زندانی $i$ و $j$ برابر با $a_{i,j}$ است. امروز با آقای پنگ تماس اضطراری گرفته‌اند و به او گفته‌اند که تا ۲۴ ساعت آینده، بمبی در این زندان منفجر خواهد شد. او باید هر چه سریع‌تر زندانیان را جابجا کند. او باید زندانیان را تا رفع خطر به یکی از دو جزیره نخیلو و مولیات تبعید کند. قدرت افراد تبعید شده به یک جزیره، برابر با بیشینه‌ میزان ارتباط بین هر جفت آن‌هاست. به صورت دقیق‌تر اگر مجموعه $S$ زندانیان تبعید شده به یک جزیره باشند، قدرت آن‌ها برابر با $\max_{i,j \in S} a_{i,j}$ خواهد بود (اگر $|S| \le 1$ قدرت آن جزیره صفر خواهد بود). به آقای پنگ کمک کنید که طوری زندانیان را بین دو جزیره تقسیم (و تبعید) کند که جمع قدرت افراد جزیره نخیلو و قدرت افراد جزیره مولیات کمینه شود. . # ورودی در سطر اول $n$، تعداد زندانیان آمده‌است. سپس در $i$ امین سطر از $n$ سطر بعدی، $n-i$ عدد آمده‌است که $j$ امین عدد برابر با $a_{i,j+i}$ است. همچنین $a_{i+j,i} = a_{i,i+j}$ $$1 \le n \le 200$$ $$0 \le a_{i,j} \le 10^9$$ # خروجی در تنها سطر خروجی کمترین قدرت زندانیان را پس از تبعید چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۱۳ | $n \le 20$ | |۲| ۶۴ | $n \le 50$ | |۳| ۲۳ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 4 5 0 2 1 3 7 2 0 4 ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 7 1 10 5 5 5 5 5 10 5 5 5 100 100 5 5 10 5 5 98 99 3 ``` ## خروجی نمونه ۲ ``` 15 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- "Let go your earthly tether. Enter the void. Empty and become wind" گورو لاقیما، راهب باستانی، اسرار بسیار زیادی با خود دفن کرده‌است. اخیرا باستان‌شناسان کتیبه‌ای کهنه متعلق به گورو پیدا کرده‌اند که روی آن تکه‌کد زیر نوشته شده‌است. move() next_node <- adj[current][pointer[current]] pointer[current] <- (pointer[current] + 1) % adj[current].size() current <- next_node cost++ seen[current] <- true move() باستان شناسان معتقدند این تکه کد، راز حرکت ستارگان و سرّ پشت طالع آدم‌ها را فاش خواهد کرد. در ادامه این کتیبه گفته‌شده است که adj بیانگر لیست مجاورت راس‌های یک درخت است و در ابتدا شرایط زیر برقرار است: + مقدار همه‌ی خانه‌های آرایه pointer برابر $0$ است. + مقدار current برابر $0$ است. + مقدار cost برابر $0$ است. + مقدار همه خانه‌های آرایه seen به‌جز خانه‌ی $0$ برابر false است و مقدار $seen[0]$ برابر با true است. پس از مدتی تحقیق، باستان‌شناسان به این نتیجه رسیدند که این روش حرکت روح گورو لاقیما بر روی یک درخت بوده و در واقع current مکان او در هر لحظه را نشان می‌دهد. بدیهی است که او تا ابد روی این درخت حرکت خواهد کرد. برای کشف راز حرکت ستارگان، باستان‌شناسان باید مقدار cost را در اولین لحظه‌ای که گورو لاقیما همه‌ی رئوس درخت را می‌بیند (همه‌ی خانه‌های آرایه seen برابر با true می‌شود) بدست آورند. توجه کنید که دانشمندان کامپیوتر توانسته‌اند ثابت کنند که چنین لحظه‌ای به ازای هر درخت و هر ترتیبی از لیست‌های مجاورت حتما وجود خواهد داشت. # ورودی در سطر اول ورودی عدد $n$ آمده‌است. در $i$ امین سطر (با شروع از صفر) از $n$ سطر بعدی ابتدا عدد $k$ آمده‌است؛ سپس $k$ عدد آمده‌است که لیست همسایه‌های راس $i$ یعنی اعداد $ adj[i]$ را نشان می‌دهد. $$1 \le n \le 300\ 000$$ $$0 \le adj_{i,j} < n$$ گراف داده‌شده درخت است. اگر یالی بین دو راس $v$ و $u$ باشد. تضمین می‌شود $u$ در لیست همسایگان $v$ ظاهر می‌شود و برعکس. # خروجی در تنها سطر خروجی، مقدار خواسته‌شده را چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۶ | $n \le 300$| |۲| ۱۱ | درجه همه رئوس درخت حداکثر $2$ است و درجه راس $0$ حداکثر $1$ است. | |۳| ۲۸ |درجه همه رئوس حداکثر $2$ است. | |۴| ۵۵ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 7 3 1 2 3 1 0 4 5 6 0 4 1 0 1 2 1 2 1 2 ``` ## خروجی نمونه ۱ ``` 14 ```

+ محدودیت زمان: ۱.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- وحید مدیرعامل مجموعه توریستی «بی‌آبان» در کویر لوط است. مهیج‌ترین بازی این مجموعه، لیز خوردن از تپه‌های شنی است. در این مجموعه $n$ تپه شنی وجود دارد که از $0$ تا $n-1$ شماره‌گذاری شده‌اند. ارتفاع تپه‌ی $i$، $h_i$ است. $m$ راه شنی تپه‌ها را به هم متصل می‌کند، راه $i$، تپه $v_i$ و $u_i$ را به یکدیگر متصل می‌کند. می‌توان از تپه $i$ به تپه $j$ لیز خورد، اگر بین این دو تپه راه شنی وجود داشته باشد و $h_j \le h_i$. وحید می‌خواهد در مجموعه‌اش بتوان از تپه $0$ شروع کرد و با لیز خوردن به تپه $n-1$ رسید. برای اینکار او می‌تواند ارتفاع تپه‌ها را تغییر دهد، برای تغییر ارتفاع تپه‌ای از $x$ به $y$ باید $|x-y|$ هزینه کند. او حق پدری بر گردن کامپیوتری‌ها دارد، به او کمک کنید و کمترین هزینه برای اینکه او به خواسته‌اش برسد را بگویید. # ورودی در سطر اول ورودی، دو عدد $n$ و $m$ آمده‌است. در سطر دوم، $n$ عدد $h_0, h_1, \dots, h_{n-1}$ آمده‌است. سپس در $i$ امین سطر از $m$ سطر بعدی، دو عدد $v_i$ و $u_i$ آمده‌است. $$1 \le n, m \le 1\ 000$$ $$0 \le h_i \le 10^9$$ $$0 \le v_i, u_i < n$$ # خروجی در تنها سطر خروجی، کمترین هزینه برای رسیدن وحید به خواسته‌اش را چاپ کنید. اگر چنین کاری ممکن نبود، $-1$ چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت | |:-------:|:----------:|:-----------:| |۱ | ۸ | $n \le 5$| |۲| ۲۱ | گراف داده شده درخت است. | |۳| ۲۸ |$n \le 100$ | |۴| ۴۳ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 3 2 30 20 10 0 1 1 2 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 2 1 10 20 0 1 ``` ## خروجی نمونه ۲ ``` 10 ``` ## ورودی نمونه ۳ ``` 3 1 1396 1396 1396 0 1 ``` ## خروجی نمونه ۳ ``` -1 ```