+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- |  | |:---:| | سرکه نماد پذیرش ناملایمات زندگی است.| یک درخت $n$ راسی داریم که در ابتدا تمام رئوسش به رنگ سرکه‌ای هستند. $q$ پرسمان به شما داده می‌شود. پرسمان‌ها از دو نوع هستند. + نوع اول: رنگ راس $v$ را عوض کنید. اگر به رنگ سرکه‌ای بود، به رنگ سبز کله غازی در بیاورید و اگر سبز کله غازی بود به رنگ سرکه‌ای در بیاورید. + نوع دوم: مجموع فاصله‌ی بین تمام جفت راس‌های به رنگ سرکه‌ای را خروجی دهید. فاصله دو راس برابر تعداد یال‌هایی است که در کوتاه‌ترین مسیر بین دو راس وجود دارد. # ورودی در سطر اول دو عدد صحیح $n$ و $q$ به‌ترتیب می‌آیند. که بیانگر تعداد راس‌ها و تعداد پرسمان‌هاست. در $n-1$ سطر بعدی در هر سطر یال‌های درخت ورودی داده می‌شود. در هر یک از $q$ سطر بعدی پرسمان‌ها می‌آیند که هر کدام به یکی از دو شکل زیر هستند. + `1 v`: رنگ راس $v$ عوض می‌شود. + `2`: مجموع فواصل را پیدا کنید. $$ 1 \le n, q \le 10^5$$ $$ 1 \le v \le n$$ # خروجی به ازای هر پرسمان از نوع دوم مجموع فواصل را در یک سطر جدید چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 3 1 2 2 3 2 1 2 2 ``` ## خروجی نمونه ۱ ``` 4 2 ``` در اولین پرسمان نوع دوم تمام رئوس به رنگ سرکه‌ای هستند و فاصله‌های تمام جفت رئوس سرکه‌ای به نحو زیر است: فاصله‌ی راس ۱ با راس ۲ برابر ۱ است، فاصله راس ۱ با راس ۳ برابر ۲ است، فاصله راس ۲ با راس ۳ برابر ۱ است. پس مجموعه فواصل رئوس به رنگ سرکه‌ای برابر ۴ است. در دومین پرسمان نوع دوم تنها رئوس ۱ و ۳ به رنگ سرکه‌ای هستند و راس ۲ به رنگ سبز کله‌ غازی است. فاصله‌ی راس ۱ با راس ۳ برابر ۲ است، پس مجموعه فواصل رئوس به رنگ سرکه‌ای برابر ۲ است. ## ورودی نمونه ۲ ``` 4 9 1 2 1 3 3 4 2 1 1 2 1 3 2 1 2 2 1 1 2 ``` ## خروجی نمونه ۲ ``` 10 6 3 0 2 ```

حل سؤال در بانک سؤالات