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

یک درخت $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$ام را نشان می‌دهد.

زیرمسئله‌ها🔗

مثال🔗

ورودی نمونه ۱🔗

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

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

طبق نظریه‌های یپکاسوالملک تنها $k$ رنگ در جهان وجود دارد. برای سادگی این رنگ‌ها را با $1$ تا $k$ شماره‌گذاری کنید. او اعتقاد دارد که اگر رنگ $j$ روی رنگ $i$ ریخته شود، رنگ $t_{i,j}$ حاصل می‌شود به طوری‌که $t_{i,j}$ نیز یکی از همان $k$ رنگ است. البته نکته‌ی عجیبی که وجود دارد این است که $t_{i, j}$ لزوما با $t_{j,i}$ برابر نیست. هم‌چنین $t_{i, i}$ لزوما برابر با $i$ نیست.

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

1. بر روی خانه‌های $i$ام تا $j$ام رنگ $c$ ریخته شود.
2. رنگ‌ خانه‌ی $i$ام چیست؟

برنامه‌ای بنویسید که بتواند پاسخ سوال‌های امتحان رنگ‌شناسی را به درستی بدهد.

ورودی🔗

در خط اول ورودی دو عدد طبیعی $n$ و $k$، تعداد خانه‌های پالت و تعداد رنگ‌ها، آمده است. در هر یک از $k$ خط بعدی، $k$ عدد طبیعی آمده است که $j$امین عدد موجود در خط $i$ام از این خطوط، نشان‌دهنده‌ی $t_{i, j}$ (رنگی که بعد از ریختن رنگ $j$ بر روی رنگ $i$ به وجود می‌آید) است. در خط بعدی $n$ عددی طبیعی آمده است که $i$امین عدد آن نشان‌دهنده‌ی رنگ ابتدایی خانه‌ی $i$ام پالت است. در خط بعدی ورودی عدد طبیعی $q$، نشان‌دهنده‌ی تعداد درخواست‌های پیکاسوالملک، آمده است. در هر یک $q$ سطر بعدی یک درخواست آمده است. درخواست‌های نوع اول، شامل یک کاراکتر # و سه عدد طبیعی $i$ و $j$ و $c$ است. درخواست‌های نوع دوم، شامل یک کاراکتر ? و یک عدد طبیعی $i$ ‌است. $2\leq k\leq 50$ $1\leq n,q\leq 200\ 000$

خروجی🔗

در خروجی، پاسخ‌ هر یک از درخواست‌های نوع دوم را در خطی جداگانه چاپ کنید.

زیرمسئله‌ها🔗

مثال🔗

ورودی نمونه ۱🔗

4 2
1 2
2 1
1 1 1 1
6
# 1 3 2
# 2 4 1
? 1
? 2
? 3
? 4

خروجی نمونه ۱🔗

2
2
2
1

ورودی نمونه ۲🔗

5 3
1 2 3
1 2 3
1 2 3
1 2 3 1 2
7
# 1 3 1
? 2
# 3 5 3
? 2
# 1 4 2
? 2
? 5

خروجی نمونه ۲🔗

1
1
2
3

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

برادران دالتون پس از فرار از زندان برای تامین مخارج روزمره‌ی زندگی به استخراج از چاه‌های نفت دوبعدی روآورده اند. یک چاه نفت دوبعدی به شکل یک جدول نامتناهی با $n$ ستون و $10^9$ سطر است که در بالای سطر اول آن، سطح زمین قرار گرفته است. هر ستون از میزان‌های مشخصی از خاک، نفت و سنگ تشکیل شده است. بر اساس نحوه‌ی به وجود آمدن نفت طی مرور زمان، در هر ستون از چاه نفت، در یک بازه‌ی صحیحی از عمق زمین نفت وجود دارد که این بازه را برای ستون $i$ام با $[l_i, r_i]$ نشان می‌دهیم و به این معناست که از عمق $l_i$ تا عمق $r_i$ از ستون $i$ام از نفت تشکیل شده است. درنتیجه این ستون شامل $r_i - l_i$ واحد نفت است. هم‌چنین می‌دانیم که همواره از سطح زمین تا عمق شروع نفت، یعنی بازه‌ی $[0, l_i]$، از خاک تشکیل شده، و از عمق پایان نفت تا انتهای چاه نفت، یعنی بازه‌ی $[r_i, 10^9]$، از سنگ تشکیل شده است. برای مثال، اگر بازه‌ی نفت در یک ستون $[1,3]$ باشد، در آن ستون، ۱ واحد خاک و ۲ واحد نفت موجود است.

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

پس از کندن یک زیرمستطیل از چاه نفت، برادران دالتون می‌توانند از تمامی منافذی که به ذخایر نفت متصل است، با استفاده از دستگاه نفت‌کِش، نفت استخراج کنند. دقت‌کنید که منظور از منافذ تمام درایه‌هایی شامل نفت از ماتریس است که پس از کَندن زیرمستطیل در معرض هوا قرار گرفته اند. به عبارت دیگر، تمام درایه‌های موجود در جدول که یکی از درایه‌های مجاور (منظور از مجاورت در این سوال، مجاورت ضلعی است. به این معنی که دو درایه ضلع مشترک داشته باشند). آن‌ها درون ‌زیرمستطیل کنده شده قرار داشته است. دستگاه نفت‌کِش پس از اتصال به یک منفذ، تمامی واحد‌های نفت که با مسیری از درایه‌های شامل نفت به منفذ می‌رسد را می‌مکد و از خروجی بیرون می‌دهد تا برادران دالتون آن‌ها را جمع آوری کنند. یک درایه‌ی شامل نفت به یک منفذ مسیر دارد، اگر دنباله‌ای از درایه‌های شامل نفت با شروع از آن خانه و پایان در منفذ موجود باشد که هر دو عضو متوالی در دنباله مجاور باشند.

حداکثر مقدار نفتی که برادران دالتون می‌توانند جمع کنند چقدر است؟

ورودی🔗

در خط اول ورودی $n$، تعداد ستون‌های چاه نفت آمده است. در $n$ خط بعدی ورودی،‌ در هر خط دو عدد طبیعی $l_i$ و $r_i$ آمده است که شروع و پایان بازه‌ی تشکیل شده از نفت در ستون $i$ام را نشان می‌دهند. $1 \le n \le 200\ 000$ $1 \le l_i \le r_i \le 10^9$

خروجی🔗

در تنها خط خروجی، حداکثر مقدار نفتی که برادران دالتون می‌توانند جمع کنند را چاپ کنید.

زیرمسئله‌ها🔗

دقت کنید همواره یک لایه خاک بر روی چاه نفت وجود دارد و در زیرمساله‌ی سوم منظور بدون درنظر گرفتن آن لایه است.

مثال🔗

ورودی نمونه ۱🔗

11
2 2
2 4
3 4
3 3
4 5
4 5
3 4
3 5
4 6
3 5
1 2

خروجی نمونه ۱🔗

11

ورودی نمونه همان شکل صفحه‌ی اول سوال است و خط ‌چین قرمز زیرمستطیلی که نفت‌کَن می‌کَند را نشان می‌دهد.