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

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

شایان از زمین‌شناسان معروف قرن $21$ است و در مورد سواحل هاوایی تحقیق می‌کند. او درختی $n$ راسی و ریشه‌دار که طبق معمول ریشه‌اش راس $1$ است را به مشتلی می‌دهد و میگوید نقشه سواحل هاوایی یکی از زیردرخت‌های این درخت است. حال مشتلی، درخت شایان و عدد $d$ را به شما ورودی می‌دهد و در قبال آن می‌خواهد به ازای هر راس مثل $v$، ارزش زیردرخت $v$ را به دست آورید.

در یک درخت ریشه‌دار، زیردرخت راس $v$ شامل تمام رئوس مانند $u$ است که در کوتاه‌ترین مسیر بین ریشه و $u$ راس $v$ ظاهر شده باشد.

ورودی🔗

در خط اول دو عدد $n$ و $d$ آمده است.

در خط بعدی $n-1$ عدد است که در جایگاه $i$ ام پدر راس $i+1$ ام آمده است.

$2 \leq n \leq 3\times10^5$ $1 \leq d \leq n$

خروجی🔗

در یک خط $n$ عدد چاپ کنید که عدد $i$ ام ارزش زیردرخت راس $i$ است.

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

مثال🔗

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

3 2 
1 2

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

2 0 0

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

11 4
1 1 2 2 3 4 5 8 8 10

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

11 7 0 0 0 0 0 0 0 0 0

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

11 3
1 1 2 2 3 4 5 8 8 10

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

11 8 0 0 3 0 0 2 0 0 0

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

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

ارشیا از بچگی علاقه‌ی زیادی به اعداد زوج داشت (این مورد همگانی است، اما در مورد او بسیار بیشتر از اکثریت افراد است) و در این ایام و بخاطر افسردگی‌های دوران قرنطینه این مورد در او به شدت افزایش پیدا کرده؛ به نحوی که در تمام کارهای روزمره‌ی خود سعی بر زوج بودن یا زوج شدن تمام چیزهای اطراف می‌کند.

او در طول روز سر و کار زیادی با اعداد و آرایه‌ها دارد و به دلیل وسواس‌های ذهنی‌اش همواره سوالات متداولی درباره‌ی این آرایه‌ها برای او پیش می‌آید. به این دلیل که این سوالات وقت و انرژی بسیار زیادی از ارشیا می‌گیرد و او به این دلیل دیگر توانایی و قدرت فکر کردن قبل را ندارد و نمی‌تواند مانند گذشته در کارهای روزمره‌اش قوی عمل کند، از شما خواسته تا با توجه به یکی از این آرایه‌ها که خودش به شما می‌دهد، تعدادی از خواسته‌های او را برآورده کنید؛

خواسته‌های ارشیا ۲ نوع مختلف هستند:

• نوع اول: یکی از اعداد آرایه را انتخاب می‌کند و از شما می‌خواهد آن را با عدد دیگری که خودش به شما می‌گوید جایگزین کنید.

• نوع دوم: یک بازه از آرایه را انتخاب می‌کند و از شما می‌پرسد «آیا در این بازه تمام اعداد مختلف زوج بار ظاهر شده‌اند یا خیر؟»

ورودی🔗

در خط اول ورودی دو عدد $n$ و $q$، که به ترتیب برابر طول آرایه و تعداد خواسته‌های ارشیا است داده می‌شود.

در خط بعدی $n$ عدد که عدد $i$ام آن برابر با $a_i$ است به شما داده می‌شود.

در $q$ خط بعدی، در هر خط ۳ عدد $t_i$، $x_i$ و $y_i$ به شما داده می‌شود که به معنای زیر هستند:

اگر $t_i = 1$: عدد $x_i$ ام را تبدیل به $y_i$ کنید.

اگر $t_i = 2$: آیا در بازه‌ی $[x_i, y_i]\:$ آرایه تمام اعداد زوج بار آمده‌اند؟

$1 \leq n, q \leq 10^6$ $1 \leq a_i \leq 10^9$

خروجی🔗

به ازای هر پرسش از نوع دوم، در صورت زوج بودن تعداد اعداد درون بازه‌ی خواسته شده، عبارت "YES" و در غیر این صورت عبارت "NO" را چاپ کنید.

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

مثال🔗

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

5 5
1 1 2 1 3
2 1 4
1 4 2
2 1 4
1 2 3
2 2 5

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

NO
YES
YES

• در پرسش اول (بازه‌ی $[1, 4]$ آرایه‌ی کنونی) آرایه برابر با $1, 1, 2, 1, 3$ است؛ پس جواب برابر "NO" است.

• در پرسش دوم (بازه‌ی $[1, 4]$ آرایه‌ی کنونی) آرایه برابر با$1, 1, 2, 2, 3$است؛ پس جواب برابر "YES" است.

• در پرسش سوم (بازه‌ی $[2, 5]$ آرایه‌ی کنونی) آرایه برابر با $1, 3, 2, 2, 3$ است؛ پس جواب برابر "YES" است.

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

6 8
3 1 2 2 1 3
2 1 6
2 1 4
2 2 5
1 1 1
2 1 4
1 5 3
2 2 5
2 3 6

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

YES
NO
YES
YES
NO
YES

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

چند روز دیگر، مسابقه حساس دربی تهران بین دو تیم استقلال و پرسپولیس برگزار می‌شود. این اولین دربی با حضور تماشاگران پس از شکست دادن ویروس کرونا می‌باشد. به همین دلیل تعداد زیادی تماشاگر به ورزشگاه می‌آیند تا تیم خود را تشویق کنند. مسئولین برگزاری مسابقه $n$ صندلی را برای تماشاگران درنظر گرفته‌اند و می‌خواهند صندلی‌ها را رنگ کنند.

همه‌ی صندلی‌ها در ابتدا سیاه هستند. مسئولین ورزشگاه از شما می‌خواهند به $q$ درخواست آن‌ها توجه کنید. هر درخواست یکی از دو نوع زیر است.

1. رنگ یکی از صندلی‌ها را به سیاه، آبی یا قرمز تغییر می‌دهند. تضمین می‌شود اگر رنگ صندلی را آبی یا قرمز بکنند، صندلی در مرحله قبل سیاه بوده است.
2. به چند روش می‌توان همه صندلی‌های سیاه را با دو رنگ آبی و قرمز رنگ کرد به طوری که تنش میان هواداران دقیقا $k$ باشد.

در روز مسابقه، هواداران پرسپولیس روی صندلی‌های قرمز و هواداران استقلال روی صندلی‌های آبی می‌نشینند. مقدار تنش میان آن‌ها برابر تعداد زوج‌ها $i < j$ است که صندلی $i$ام آبی و صندلی $j$ام قرمز باشد. به مسئولین مسابقه پاسخ درخواست‌های نوع دوم را بدهید.

ورودی🔗

در خط اول $n$ تعداد صندلی‌ها و $q$ تعداد درخواست‌ها به ترتیب می‌آیند.

هر یک از $q$ خط بعدی به یکی از دو شکل زیر هستند.

در خط اول $n$ تعداد صندلی‌ها و $q$ تعداد درخواست‌ها به ترتیب می‌آیند.

هر یک از $q$ خط بعدی به یکی از دو شکل زیر هستند.

درخواست نوع اول: 1 x c مسئولین رنگ صندلی $x$ام را به رنگ $c$ درمی‌آورند. قرمز را با $R$، آبی را با $B$ و سیاه را با $X$ نمایش می‌دهند.

درخواست نوع دوم: 2 k به چند روش می‌توان صندلی‌های سیاه را آبی و قرمز کرد که تنش میان هواداران دقیقا $k$ باشد.

$2 \leq n \leq 100$ $1 \leq q \leq 100$

خروجی🔗

باقی‌مانده تقسیم جواب هر درخواست نوع دوم بر $10^9+7$ را در خطی جدید چاپ کنید.

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

مثال🔗

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

3 6
1 1 B
2 2
1 2 B
2 2
1 3 R
2 2

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

2
1
1

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

3 4
1 1 B
1 2 B
2 2
2 1

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

1
0

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

6 9
1 3 B
2 4 
1 3 X
2 4
1 5 B
1 1 R
1 2 B
1 6 B
2 3

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

5
11
0

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

3 7
2 2
1 1 B
2 2
1 1 X
1 1 R
2 3
2 1

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

2
2
0
1

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

علی بعد از دیدن فیلم انگاشته (Tenet) ایده‌ی سوال زیر به ذهنش رسید ولی توانایی حل آن را نداشت. به وی کمک کنید تا آن را حل کند.

کیانوش ناباورانه به شهر عجیب غریبی به اسم برره می‌رسد. در برره $n$ روستا وجود دارد که بعضی از آن‌ها با $m$ جاده دوطرفه به هم متصل شده‌اند، به طوری که از هر روستا می‌توان به بقیه روستاها رفت. جاده‌ی $i$ام روستای $v_i$ و $u_i$ را به هم وصل می‌کند. برای اینکه کیانوش از جاده $i$ام عبور کند، نظام دوبرره از او $a_i$ ریال می‌گیرد و به او کوپن جاده‌ی $i$ام را می‌دهد. همچنین او می‌تواند هنگام گذرکردن از جاده $i$ام کوپن همان جاده را به نظام دوبرره پس بدهد و با پرداخت $b_i$ ریال از آن عبور کند. در روش دوم نظام دوبرره به کیانوش کوپن نمی‌دهد.

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

برای گرفتن اقامت برره، کیانوش باید به تعدادی روستا برود و رضایت اهالی آنجا را کسب کند. کیانوش دنباله $\langle x_1, x_2, ..., x_k \rangle$ روستاها را دارد و باید آن روستاها را به ترتیب ببیند. او از روستای $x_1$ شروع می‌کند، سپس باید با طی کردن تعدادی جاده به روستای $x_2$ برود، سپس با طی کردن تعدادی جاده دیگر به روستای $x_3$ برود، ... و در نهایت به روستای $x_k$ برود. کیانوش به حداقل چقدر پول احتیاج دارد تا بتواند اقامت برره را بگیرد.

ورودی🔗

در خط اول سه عدد $n$ تعداد روستاها، $m$ تعداد جاده‌ها و $k$ طول دنباله‌ی روستاها به ترتیب می‌آیند.

در $i$امین خط از $m$ خط بعدی، چهار عدد $v_i$، $u_i$، $a_i$ و $b_i$ نمایانگر جاده $i$ام به ترتیب می‌آیند.

در خط بعدی $k$ عدد $x_1, x_2, ..., x_k$ به ترتیب می‌آیند.

تضمین می‌شود گراف شهر برره همبند است.

$1 \leq n, k \leq 150$ $n-1 \leq m \leq \binom{n}{2}$

$1 \le u_i, v_i \le n,~~ u_i \neq v_i$

$1 \le b_i \le a_i \le 10^9$

خروجی🔗

در خروجی تنها یک عدد خروجی دهید که کمترین پولی است که کیانوش برای گرفتن اقامت باید به نظام دوبرره پرداخت کند.

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

مثال🔗

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

4 6 10
1 2 3 1
1 3 4 2
1 4 6 3
2 3 1 1
2 4 3 2
3 4 8 4
1 4 2 3 2 4 1 3 2 4

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

24

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

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

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

26

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

7 8 3
1 2 5 1
2 4 5 1
1 3 4 3
3 4 4 3
4 5 3 1
5 7 3 1
4 6 3 2
6 7 2 1
1 7 1

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

20

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

مهرداد به تازگی فهمیده که با جایگشت فروشی می‌تواند پول خوبی بدست بیاورد. مهرداد مغازه‌ای خرید و حال می‌خواهد از هر جایگشت یکی بخرد و به مغازه‌اش بیاورد. آرین دلال جایگشت‌ها است و قیمت گذاری جایگشت‌ها را او تعیین می‌کند. او که از المپیاد کامپیوتری‌های سابق می‌باشد، به روش عجیبی قیمت‌گذاری را انجام می‌دهد که در ادامه با آن آشنا می‌شوید.

جایگشت $\langle p_1, p_2, ..., p_n \rangle$ را در نظر بگیرید.

قدرت عضو $i$ام را با $a_i$ نشان می‌دهیم. بزرگترین عدد $j$ را در نظر بگیرید که $j < i$ و $p_j > p_i$ باشد. اگر هیچ $j$ با خواص گفته شده وجود نداشته باشد، آنگاه $a_i = 1$ و در غیر این صورت $a_i = a_j + 1$ می‌باشد.

همت عضو $i$ام را با $b_i$ نشان می‌دهیم. کوچکترین عدد $j$ را در نظر بگیرید که $j > i$ و $p_j > p_i$ باشد. اگر هیچ $j$ با خواص گفته شده وجود نداشته باشد، آنگاه $b_i = 1$ و در غیر این صورت $b_i = b_j + 1$ می‌باشد.

آرین یک عدد طبیعی $k$ انتخاب می‌کند و قیمت جایگشت $\langle p_1, p_2, ..., p_n \rangle$ را برابر $\sum_{i=1}^{n} (a_i + b_i)^k$ قرار می‌دهد. مهرداد که می‌خواهد از هر جایگشت دقیقا یکی بخرد، از شما می‌خواهد به او بگویید به چه مقدار پول احتیاج دارد.

ورودی🔗

در خط اول دو عدد طبیعی $n$ و $k$ به ترتیب می‌آیند. $2 \leq n \leq 5000$

$0 \leq k \leq 5000$

خروجی🔗

باقیمانده تقسیم مقدار پولی که مهرداد باید برای خرید تمامی جایگشت‌ها به آرین پرداخت کند بر $10^9 + 7$ را چاپ کنید.

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

مثال🔗

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

2 1

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

10

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

5 2

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

7928

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

5 3

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

32376

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

124 274

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

796626652

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

مبین و مبینا می‌خواهند با بازی فکری جدیدی که پدربزرگشان، مستربین برایشان خریده است بازی کنند. مبین دفترچه راهنمای بازی را می‌خواند و بازی را برای مبینا شرح می‌دهد:

«این بازی فقط از تعدادی آجر تشکیل شده است. در ابتدا آجرها را در $n$ ردیف بچینید و در ردیف $i$ام $a_i$ آجر را روی هم قرار دهید. شما در هر دقیقه می‌توانید تعدادی ردیف متوالی که تعداد آجرهای آن‌ها به یک اندازه است را انتخاب کنید و به همه‌ی آن‌ها به تعداد مساوی آجر اضافه کنید یا از آجر‌هایش بکاهید. به عبارتی دیگر می‌توانید یک بازه $l \leq r$ و عدد صحیح $x$ انتخاب کنید به طوری که $a_i = a_l$ به ازای تمامی $l \leq i \leq r$ برقرار باشد، سپس به تمامی اعضای این بازه را با $x$ جمع کنید.

به طور مثال اگر دنباله $a = \langle 4, 2, 2, 2, 3, 2 \rangle$باشد، می‌توانید با انتخاب بازه $l = 2$ و $r = 3$ و عدد صحیح $x = -1$ دنباله را به $a = \langle 4, 1, 1, 2, 3, 2 \rangle$ تبدیل کنید.

هدف بازی این است که در کمترین زمان ممکن کاری کنید که همه‌ی ردیف‌ها به یک اندازه آجر داشته باشند.»

مبین و مبینا که خیلی کوچک هستند از پس این بازی برنمی‌آیند و از شما کمک می‌خواهند تا کمترین زمان ممکن برای انجام بازی را پیدا کنید.

ورودی🔗

در خط اول $n$ تعداد ردیف‌ها می‌آیند.

در خط دوم $n$ عدد $a_1, a_2, ..., a_n \:$ به ترتیب می‌آیند.

$2 \leq n \leq 750$ $1 \leq a_i \leq n$

خروجی🔗

کمترین زمان ممکن برای برابر کردن تعداد آجرهای تمامی ردیف‌ها را چاپ کنید.

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

مثال🔗

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

5
1 2 3 3 1

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

2

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

5
1 3 2 1 3

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

3

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

دان دریایی کاراییب در زندانی قرار دارند که به شکل جدولی $n \times n$است. از آنجایی که جک در جوانی المپیاد کامپیوتری بوده کامپیوتر مرکزی زندان را هک کرده و متوجه شده است که اتاق آن ها در خانه $(1, 1)$ جدول و در خروجی زندان در خانه $(n, n)$ قرار دارد.

هر کدام از خانه‌های جدول یک اتاق است که چهار در دارد که هر کدام روی یکی از ضلع های مربع هستند.

جک بعد از هک کردن کامپیوتر مرکزی متوجه شد که بعضی از خانه‌های جدول مین گذاری شده‌اند. طبعا هیچ‌کس دوست ندارد از روی مین رد بشود. حالا مسئله این است که جک می‌خواهد گروهش را به بیشترین تعداد دسته ممکن افراز کند و هر گروه از یک مسیر جدا برود. به این معنی که جک نیاز دارد بیشترین تعداد مسیر فرار ممکن را بداند به طوریکه هیچ اتاقی در دو مسیر دیده نشود (به جز اتاق شروع و پایان). و البته واضح است که این بیشترین تعداد مسیر ممکن حداکثر ۲ هست.

حالا قرار است جک به شما مختصات مین ها را یکی یکی بدهد و بعد از هر کوئری شما بیشترین تعداد مسیر ممکن را بگویید!

پیاده‌سازی🔗

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

بنابراین جک نمی‌تواند مختصات مین‌ها را برای شما بفرستد پس از شما می‌خواهد تابعی پیاده سازی کنید که جواب مسئله را بدهد. یعنی در این سوال شما اجازه خواندن از ورودی یا نوشتن در خروجی را ندارید. شما باید توابع زیر را پیاده سازی کنید و جک از آنها استفاده می‌کند. همچنین برنامه شما نباید تابع main داشته باشد.

در صورت هرگونه تلاش برای خواندن از ورودی یا نوشتن در خروجی یا استفاده از تابع exit نمره شما صفر می‌شود.

void init(int n, int q)

شما باید این تابع را پیاده‌سازی کنید. در ابتدای فرایند این تابع تنها یک بار صدا زده می‌شود و مقادیر $n, q$ را به شما می‌دهد.

• n: اندازه طول و عرض زندان
• q: bomb تعداد بار‌های فراخوانی تابع

int bomb(int x, int y)

شما باید این تابع را پیاده‌سازی کنید. جک با صدا زدن این تابع به شما مختصات یک مین جدید را می‌دهد. خروجی این تابع باید بیشترین تعداد مسیر فرار ممکن با اطلاعات فعلی باشد.

$2 \leq n \leq 3000$

$1 \leq q \leq min(2\times10^5, n^2-2)$

$1 \leq x,y \leq n$

تضمین می‌شود که $x,y$ ها غیر‌تکراری هستند. همچنین خانه شروع و پایان هیچوقت مین‌گذاری نمی‌شوند.

ارزیاب نمونه🔗

دو تابع خواسته شده را در فایل TheGreatEscape.cpp پیاده‌سازی کنید. لازم نیست جواب شما تنها شامل این دو تابع باشد بلکه بسته به نیاز خود می‌توانید توابع دیگر نیز تعریف کنید. ولی برنامه شما نباید تابع main داشته باشد.

برای کامپایل کردن برنامه باید compile_cpp.sh را اجرا کنید.

حاصل کامپایل فایل اجرایی TheGreatEscape خواهد بود که همان ارزیاب نمونه است.

سپس فایل اجرایی TheGreatEscape را که توسط compile_cpp.sh تولید شده است،‌ اجرا کنید.

ارزیاب نمونه در خط اول اعداد $n,q$ را به ترتیب می‌خواند.

سپس $q$ خط دیگر می‌خواند که در هر کدام ابتدا عدد $x$ و سپس $y$ آمده است. هر خط نشان دهنده یک کوئری انفجار مین است.

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

مثال🔗

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

5 7
4 1
3 2
2 3
3 3
3 4
1 4
4 5

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

2211100

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

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

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

222222

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

9 18
6 6
3 4
3 1
6 8
3 2
6 4
3 5
6 7
3 3
3 7
6 5
6 3
6 9
3 6
2 5
4 1
7 6
1 5

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

222222222222221110

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

مالک بعد از تصاحب ثروت ریزآبادی‌ها بسیار پولدار شد. سپس برای پسرش میثم باغ بزرگی خرید و در آن $n$ گل در یک ردیف کاشت. هر گل بویی دارد و $i$امین بو از سمت چپ $a_i$ واحد بو دارد. میثم هر روز هنگام غروب خورشید، به باغش می‌رود و از سمت چپ به سمت راست باغ حرکت می‌کند. اگر به گلی برسد که بوی آن را حس نکند بسیار خشمگین می‌شود و تمام باغ را آتش می‌زند. او بوی گل $i > 1$ را حس نمی‌کند اگر $a_i < a_{i-1}$ باشد.

مالک که از این موضوع آگاه است $n$ تا اسپری خریده است تا هر روز صبح به گل‌ها بزند و بوی آن‌ها را فقط در آن روز مقداری بیشتر کند. برای اینکه بوی گل $i$ام را یک واحد افزایش دهد، باید یک پیس از اسپری $i$ام به آن بزند. قیمت هر پیس از اسپری $i$ام $b_i$ تومان می‌باشد. گاهی اسپری‌ها کیفیت لازم را ندارند و قیمت آن‌ها منفی می‌شود! قابل ذکر است که بوی گل‌ها نمی‌تواند از $10^6$ بیشتر شود.

مالک در $q$ روز بعدی، وقتی به باغ برود بوی یکی از گل‌ها افزایش می‌یابد. در روز $i$ام مقدار $a_{x_i}$ به اندازه $y_i > 0$ بیشتر می‌شود. او که بسیار پول‌پرست است، می‌خواهد با کمترین هزینه ممکن، هر روز باغ را باب میل پسرش کند. به او کمک کنید تا این هزینه را در هر روز پیدا کند.

ورودی🔗

در خط اول $n$ و $q$، تعداد گل‌ها و تعداد روزهابه ترتیب می‌آیند.

در خط دوم $n$ عدد $a_1, a_2, ..., a_n$ به ترتیب می‌آیند.

در خط سوم $n$ عدد $b_1, b_2, ..., b_n$ به ترتیب می‌آیند.

در $i$امین خط از $q$ خط بعدی، دو عدد $y_i$ و $x_i$ به ترتیب می‌آیند.

$2 \leq n, q \leq 200\,000$

$-10^6 \leq a_i, b_i \leq 10^6$

$1 \leq x \leq n$

$1 \leq y \leq 10^6$

تضمین می‌شود بوی تمامی گل‌ها هیچوقت از $10^6$ بیشتر نمی‌شود.

خروجی🔗

در $q$ خط، به ازای هر روز که مالک وارد باغ می‌شود، کمترین هزینه برای اینکه باغ را باب میل میثم کند را چاپ کنید.

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

مثال🔗

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

3 3
4 9 6
-1 3 0
3 4
1 6
3 5

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

-5
3
3

در نمونه اول، روز اول دنباله گل‌ها $\langle 4, 9, 10 \rangle$ می‌باشد. مالک می‌تواند ۵ بار به اولین گل اسپری بزند و دنباله گل‌ها $\langle 9, 9, 10 \rangle$ می‌شود و ۵- تومان خرج کند.

در روز دوم دنبال بوی گل‌ها $\langle 10, 9, 10 \rangle$ می‌باشد. مالک می‌تواند یک بار به دومین گل اسپری بزند و دنباله گل‌ها $\langle 10, 10, 10 \rangle$ می‌شود و ۳ تومان خرج کند.

در روز سوم دنباله گل‌ها $\langle 10, 9, 15 \rangle$ می‌شود و مشابه روز دوم کافی است مالک یک بار به دومین گل اسپری بزند.

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

6 3
3 1 3 2 4 4
1 -5 1 1 1 1
1 3
5, 6
2 999999

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

-1000008
-1000014
3999981

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

جک پس از اینکه گاو خود را با لوبیای سحرآمیز پیر دانا عوض کرد، آن را کاشت و سپس خوابید. روز بعد که بیدار شد دید که لوبیا رشد کرده و تبدیل به یک درخت عجیب شده است. این درخت دارای $n$ لوبیا است که هر لوبیا یک خوشمزگی از $1$ تا $n$ دارد و به ازای هر عدد از $1$ تا $n$ دقیقا یک لوبیا با آن خوشمزگی وجود دارد. به لوبیا با خوشمزگی $i$ لوبیای $i$ می‌گوییم.

در این درخت دقیقا $n-1$ چوب وجود دارد که چوب $i$م لوبیا $u_i$ و $v_i$ را به هم وصل می‌کند. می‌گوییم دو لوبیا $x$ و $y$ به هم مسیر دارند اگر و تنها اگر دنباله‌ای از لوبیا‌ها مانند $\langle a_1, a_2, ..., a_k\rangle$ وجود داشته باشد که $a_1 = x, a_k = y$ و بین هر دو عضو متوالی از این دنباله چوب وجود داشته باشد.

میدانیم که پیر دانا تضمین کرده که بین هر دو لوبیا مسیر وجود دارد.

حال مادر جک میخواهد برای ناهار قورمه‌سبزی(!) درست کند و برای این کار می‌خواهد تعدادی از لوبیا‌های درخت را بکَنَد و با آنها غذا درست کند. اگر او بخواهد لوبیای $i$ را بکَنَد مجبور است تمام چوب‌های متصل به آن را نیز بشکند. طبق دستور پختی که از مادربزرگ جک به مادر جک رسیده نباید در قورمه‌سبزی طعم لوبیا‌ها تفاوت داشته باشند. برای همین او دو عدد $l$ و $r$ انتخاب می‌کند که $1 \leq l \leq r \leq n$ باشد. سپس تمامی لوبیا‌هایی که خوشمزگی آنها بین $l$ و $r$ است (شامل خود $l$ و $r$) را می‌کَنَد و در غذا می‌ریزد.

پیر دانا که توانسته بود پیش‌بینی کند که مادر جک می‌خواهد با لوبیا‌های درخت سحرآمیز قورمه‌سبزی درست کند به مادر جک هشدار داد که این درخت جادویی است و اگر پس از کندن لوبیاها، لوبیایی باقی نماند یا اینکه دو لوبیا باقی بمانند که به هم مسیر نداشته باشند، درخت جک و مادرش را نفرین می‌کند و به سنگ تبدیل می‌کند !!

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

حال پیر دانا که بسیار نگران جک و مادرش است می‌خواهد بداند که مادر جک به چند طریق می‌تواند دو عدد $l$ و $r$ را انتخاب کند که سنگ نشوند. از آنجایی که در روستا کامپیوتر وجود ندارد، پیر دانا از شما میخواهد برنامه‌ای بنویسید که جواب پرسش پیرمرد را بدهد.\

پیر دانا به شما توصیه می‌کند که به ورودی‌های نمونه توجه کنید تا خواسته‌ی او را بهتر متوجه شوید.

ورودی🔗

در خط اول ورودی عدد $n$ که تعداد لوبیا‌های درخت است داده می‌شود.

در $n-1$ خط بعدی ورودی در خط $i$م دو سر چوب‌های درخت‌ به ترتیب داده می‌شوند. در خط $i$ دو عدد$u_i$ و$v_i$ داده می‌شود که یعنی چوبی بین لوبیا‌ی $u_i$ و $v_i$ وجود دارد. $1 \leq n \leq 10^6$ $1 \le u_i, v_i \le n~~,~~ u_i \neq v_i$

بین هر دو لوبیا مسیر وجود دارد.

خروجی🔗

در خروجی تنها یک عدد خروجی دهید که برابر تعداد جفت $l$ و $r$ است که با کندن آنها جک و مادرش نفرین نمی‌شوند.

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

مثال🔗

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

4
1 2
2 4
3 4

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

6

لوبیاها را با دایره و چوب‌ها را با خط نشان دهیم. اگر لوبیاهای کنده شده را با ضربدر مشخص کنیم، حالت‌های مطلوب نمونه ورودی اول 6 حالت زیر می‌باشد.

و برای مثال حالت زیر نامطلوب است چون لوبیای شماره $1$ به لوبیای شماره $3$ مسیر ندارد.

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

6
1 6
6 5
5 2
1 3
4 1

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

10

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

9
1 3
9 2
3 5
2 4
7 4
1 2
1 8
3 6

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

23