+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- خانج شخصیتی تپل‌ (شما بخوانید تو‌پر) و کم حاشیه است! او به تازگی تصمیم گرفته رژیم بگیرد و معمولا به رژیم خود پایبند است. خانج تنها زمانی که درختی ببیند که رئوس آن رنگ شده اند، کنترل خود را از دست می‌دهد، و اگر در درخت بیشینه‌ی فاصله‌ی بین دو راس ناهمرنگ $x$ باشد، او $x$ جوس شیرینی خواهد خورد.(جوس یک واحد اندازه‌گیری شیرینی است که با توجه به وقت محدود امتحان به توضیح آن نمی‌پردازیم) درختی داریم با $n$ راس و $k$ رنگ، رنگ بعضی از رئوس را نمی‌دانیم، رنگ آنها با عدد $0$ نشان داده شده و رنگ بقیه رئوس با اعداد $1$ تا $k$. از آنجا که ما به شدت نگران وضعیت رژیم خانج هستیم به دنبال آن هستیم که او با دیدن این درخت کمترین مقدار شیرینی را بخورد. پس تلاش می‌کنیم رئوسی که رنگشان معلوم نیست را طوری با رنگ‌های $1$ تا $k$ رنگ کنیم که رنگ $i$ام $a_{i}$ بار ظاهر شود و بیشینه‌ی فاصله‌ی میان $2$ راس ناهمرنگ کمینه شود. تضمین می‌شود که جمع رنگ‌ها $n$ است. همچنین $q$ بار یک راس انتخاب شده، و رنگ آن تغییر می‌کند، به این صورت که اگر رنگش $1$ تا $k$ باشد٬ رنگ آن $0$ می‌شود(بی‌رنگ می‌شود) و اگر بی‌رنگ باشد رنگ آن به عددی از $1$ تا $k$ تبدیل می‌شود(تضمین می‌شود بعد از این عمل هیچ رنگ $i$ای بیش از $a_{i}$ بار ظاهر نخواهد شد) از شما خواسته شده $q + 1$ عدد چاپ کنید، که نشان‌دهنده‌ی این است که در ابتدا و بعد از هر تغییر در درخت، خانج حداقل چند جوس شیرینی خواهد خورد؟ # ورودی در سطر اول ورودی دو عدد $n$ و $k$ آمده‌است. در $n - 1$ سطر بعد هر خط، دو عدد $u$ و $v$ آمده است، که به معنی وجود یالی از راس $u$ به راس $v$ می‌باشد. در سطر بعدی $k$ عدد آمده است که عدد $i$ام برابر با $a_{i}$ است. در سطر بعدی عدد $q$ آمده است. در $q$ سطر بعدی، هر سطر $2$ عدد $x$ و $c$ آمده است، که به معنی تغییر رنگ راس $x$ به رنگ $c$ می‌باشد. اگر $c = 0$ باشد، به این معنا‌ست که این راس بی‌رنگ شود. $$1 \le n, k, q \le 100\ 000$$ $$1 \le u, v, x \le n$$ $$ 0 \le c \le k$$ # خروجی در $q + 1$ سطر خروجی، مقدار‌های گفته شده در صورت سوال را به ترتیب چاپ کنید. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۱۵ | $q \le 10$ ,$n \le 9$| | ۲ | ۱۵ | $k = 2$ ,$q = 0$ | | ۳ | ۲۰ | $q = 0$| | ۴ | ۵۰ | بدون محدودیت اضافی| # مثال ## ورودی نمونه ۱ ``` 3 2 1 2 2 3 2 1 4 1 1 2 1 2 0 2 2 ``` ## خروجی نمونه ۱ ``` 1 1 2 1 1 ```

خانج

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

خانج شخصیتی تپل‌ (شما بخوانید تو‌پر) و کم حاشیه است! او به تازگی تصمیم گرفته رژیم بگیرد و معمولا به رژیم خود پایبند است.

خانج تنها زمانی که درختی ببیند که رئوس آن رنگ شده اند، کنترل خود را از دست می‌دهد، و اگر در درخت بیشینه‌ی فاصله‌ی بین دو راس ناهمرنگ $x$ باشد، او $x$ جوس شیرینی خواهد خورد.(جوس یک واحد اندازه‌گیری شیرینی است که با توجه به وقت محدود امتحان به توضیح آن نمی‌پردازیم)

درختی داریم با $n$ راس و $k$ رنگ، رنگ بعضی از رئوس را نمی‌دانیم، رنگ آنها با عدد $0$ نشان داده شده و رنگ بقیه رئوس با اعداد $1$ تا $k$ . از آنجا که ما به شدت نگران وضعیت رژیم خانج هستیم به دنبال آن هستیم که او با دیدن این درخت کمترین مقدار شیرینی را بخورد. پس تلاش می‌کنیم رئوسی که رنگشان معلوم نیست را طوری با رنگ‌های $1$ تا $k$ رنگ کنیم که رنگ $i$ ام $a_{i}$ بار ظاهر شود و بیشینه‌ی فاصله‌ی میان $2$ راس ناهمرنگ کمینه شود. تضمین می‌شود که جمع رنگ‌ها $n$ است.

همچنین $q$ بار یک راس انتخاب شده، و رنگ آن تغییر می‌کند، به این صورت که اگر رنگش $1$ تا $k$ باشد٬ رنگ آن $0$ می‌شود(بی‌رنگ می‌شود) و اگر بی‌رنگ باشد رنگ آن به عددی از $1$ تا $k$ تبدیل می‌شود(تضمین می‌شود بعد از این عمل هیچ رنگ $i$ ای بیش از $a_{i}$ بار ظاهر نخواهد شد)

از شما خواسته شده $q + 1$ عدد چاپ کنید، که نشان‌دهنده‌ی این است که در ابتدا و بعد از هر تغییر در درخت، خانج حداقل چند جوس شیرینی خواهد خورد؟

ورودی🔗

در سطر اول ورودی دو عدد $n$ و $k$ آمده‌است.

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

در سطر بعدی $k$ عدد آمده است که عدد $i$ ام برابر با $a_{i}$ است.

در سطر بعدی عدد $q$ آمده است.

در $q$ سطر بعدی، هر سطر $2$ عدد $x$ و $c$ آمده است، که به معنی تغییر رنگ راس $x$ به رنگ $c$ می‌باشد. اگر $c = 0$ باشد، به این معنا‌ست که این راس بی‌رنگ شود.

$1 \le n, k, q \le 100\ 000$ $1 \le u, v, x \le n$ $0 \le c \le k$

خروجی🔗

در $q + 1$ سطر خروجی، مقدار‌های گفته شده در صورت سوال را به ترتیب چاپ کنید.

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

زیرمسئله	نمره	محدودیت
۱	۱۵	$q \le 10$ , $n \le 9$
۲	۱۵	$k = 2$ , $q = 0$
۳	۲۰	$q = 0$
۴	۵۰	بدون محدودیت اضافی

مثال🔗

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

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