====== 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| * [[سوال ۲|سوال بعد]]