المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۲۳:عملی مقدماتی اول:سوال ۳

مسابقات بدنسازی

آقا داوود $N$ شاگرد دارد که می‌خواهد آن‌ها را برای مسابقات بدن‌سازی آماده کند. برای این‌کار قرار است به هر شاگردش یک باشگاه بدنسازی‌ معرفی کند تا در آن بتواند خود را برای مسابقات آماده کند. از طرفی چون شاگردان آقا داوود با یکدیگر رابطه خوبی ندارد، هیچ دوتایی از آن‌ها نمی‌خواهند در درون یک باشگاه تمرین کنند. می‌دانیم شهری که آقا داوود در آن زندگی می‌کند، $2N$ تقاطع دارد که به وسیله‌ی جاده‌هایی دو طرفه به یکدیگر متصل می‌شوند و در درون هر تقاطع یا یک باشگاه بدنسازی قرار دارد یا خانه‌ی یکی از شاگردان آقا داوود است. علاوه بر این بین هر دو تقاطع در شهر مسیر یکتایی وجود دارد (در واقع یک درخت داریم). از آن‌جا که آقا داوود خیلی به فکر راحتی شاگردانش است، می‌خواهد طوری باشگاه‌ها را به آن‌ها معرفی کند که مجموع فاصله‌ی شاگردان با باشگاهشان کمینه شود. آقا داوود را در این کار کمک کنید.

ورودی

  • در سطر اول ورودی عدد صحیح $N$ آمده است ($1\leq N \leq 50000$) .
  • در سطر بعدی $N$ عدد متمایز، $1\leq a_1, a_2, \cdots, a_N \leq 2N$ آمده است که بیانگر شماره تقاطع های شاگردان آقا داوود است.
  • در هریک از $2N-1$ خط بعدی دو عدد $V$ و $U$ آمده است که بیانگر یک جاده دوطرفه بین این تقاطع‌ها است ($U\neq V, 1\leq U, V \leq 2N$).
  • در حداقل ۴۰ درصد از ورودی‌ها، $1\leq N \leq 1000$ است .

خروجی

در تنها سطر خروجی مجموع فاصله‌ی شاگردان تا باشگاه اختصاص داده شده را در حالت بهینه، چاپ کنید.

محدودیت‌ها

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

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
3
1 2 4
1 2
4 5
2 4
6 1
3 5
5

ابزار صفحه