+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک درخت $n$ راسی به شما داده شده است که راس‌های آن از $1$ تا $n$ شماره گذاری شده اند. هر راس در این درخت با یکی از رنگ‌های $1$ تا $k$ رنگ‌آمیزی شده است. مقدار مطلوبیت هر راس به شکل زیر تعریف می‌شود: + فرض کنید پس از کندن راس $v$ از درخت، $t$ مولفه‌ی همبندی به وجود بیاید. این مولفه‌ها را $a_1, a_2, ..., a_t$ می‌نامیم. + به ازای هر مولفه $a_i$، مجموعه‌ی رنگ‌های راس‌های آن را $s_i$ می‌نامیم. دقت‌کنید که در مجموعه عضو تکراری نداریم و اندازه‌ی یک مجموعه برابر با تعداد اعضای متفاوت آن می‌باشد. + مقدار مطلوبیت راس $v$ برابر است با $\sum_{i=1}^t{|s_i|}$. مقدار مطلوبیت تمام راس‌های درخت را محاسبه کنید. # ورودی در خط اول ورودی دو عدد طبیعی $n$ و $k$، نشان‌دهنده‌ی تعداد راس‌های درخت و حداکثر شماره‌ی رنگ راس‌های درخت، آمده است. در خط دوم ورودی $n$ عدد طبیعی $c_1, c_2, ..., c_n$، نشان‌دهنده‌ی رنگ‌های راس‌های درخت، آمده است. در $n-1$ خط بعدی ورودی، در هر خط دو عدد طبیعی $v_i$ و $u_i$ آمده است که نشان‌دهنده‌ی وجود یک یال بین دو راس $v_i$ و $u_i$ است. تضمین می‌شود گراف ورودی درخت است. $$1 \le k \le n \le 300\ 000$$ $$1 \le c_i \le k$$ $$1 \le u_i, v_i \le n$$ # خروجی در تنها خط خروجی، $n$ عدد چاپ کنید که عدد $i$ام مقدار مطلوبیت راس $i$ام را نشان می‌دهد. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۸ | $n \le 1\ 000$ | | ۲ | ۸ | $k \le 10$ | | ۳ | ۸ | درخت داده شده مسیر است. | | ۴ | ۱۹ | از هر رنگ حداکثر دو راس موجود است. | | ۵ | ۵۷ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 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 ```