المپدیا

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

ابزار کاربر

ابزار سایت


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

Notdesirable

یک درخت $n$ راسی به شما داده شده است که راس‌های آن از $1$ تا $n$ شماره گذاری شده اند. هر راس در این درخت با یکی از رنگ‌های $1$ تا $k$ رنگ‌آمیزی شده است.

مقدار مطلوبیت هر راس به شکل زیر تعریف می‌شود:

  • فرض کنید پس از کندن راس $v$ از درخت، $t$ مولفه‌ی همبندی به وجود بیاید. این مولفه‌ها را $a_1, a_2, \dots, a_t$ می‌نامیم.
  • به ازای هر مولفه $a_i$، مجموعه‌ی رنگ‌های راس‌های آن را $s_i$ می‌نامیم. دقت‌کنید که در مجموعه عضو تکراری نداریم و اندازه‌ی یک مجموعه برابر با تعداد اعضای متفاوت آن می‌باشد.
  • مقدار مطلوبیت راس $v$ برابر است با $\sum_{i=1}^t{|s_i|}$.

مقدار مطلوبیت تمام راس‌های درخت را محاسبه کنید.

ورودی

در خط اول ورودی دو عدد طبیعی $n$ و $k$، نشان‌دهنده‌ی تعداد راس‌های درخت و حداکثر شماره‌ی رنگ راس‌های درخت، آمده است.

در خط دوم ورودی $n$ عدد طبیعی $c_1, c_2, \dots, c_n$، نشان‌دهنده‌ی رنگ‌های راس‌های درخت، آمده است.

در $n-1$ خط بعدی ورودی، در هر خط دو عدد طبیعی $v_i$ و $u_i$ آمده است که نشان‌دهنده‌ی وجود یک یال بین دو راس $v_i$ و $u_i$ است.

خروجی

در تنها خط خروجی، $n$ عدد چاپ کنید که عدد $i$ام مقدار مطلوبیت راس $i$ام را نشان می‌دهد.

زیرمسئله‌ها

  • زیرمسئله اول (۸ نمره): $n \le 1000$
  • زیرمسئله دوم (۸ نمره): $k \le 10$
  • زیرمسئله سوم (۸ نمره): درخت داده شده مسیر است.
  • زیرمسئله چهارم(۱۹ نمره): از هر رنگ حداکثر دو راس موجود است.
  • زیرمسئله پنجم(۵۷ نمره): بدون محدودیت اضافی

محدودیت‌ها

  • محدودیت زمان: ۲ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت
  • $1 \le k \le n \le 3 \times 10^5$
  • $1 \le c_i \le k$
  • $1 \le u_i, v_i \le n$
  • تضمین می‌شود گراف ورودی درخت است.

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

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

ابزار صفحه