+ محدودیت زمان: ۴ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی که در این گرمای تابستان اعضای شرکت را به اسکیپ روم برده بود برای رفع خستگی تصمیم می‌گیرد برای آن‌ها نوشابه بخرد... اما می‌خواهد تنها برای افرادی نوشابه بخرد که بتوانند سوالات زیر را درباره گراف پاسخ دهند...* فرض کنید $G$ یک گراف وزن دار بدون جهت **همبند** باشد. $G$ دارای $n$ راس و $m$ یال است. هر یال $G$ دو راس مختلف را به هم متصل می‌کند. همچنین راس‌های این گراف با ۱ تا $n$ شماره گذاری شده‌اند. روی راس شماره $i$ عدد $a_i$ نوشته شده است. از ما تعدادی سوال پرسیده می‌شود. در هر سوال سه عدد $v$ و $x$ و $k$ داده می‌شود و از ما کوچک‌ترین مقدار $w$ را می‌خواهند که حداقل $k$ راس وجود داشته باشند که فاصله آن‌ها از $v$ فاصله حداکثر $w$ باشد و عدد نوشته شده روی آن نسبت به $x$ اول باشد. منظور از وزن یک مسیر بزرگ ترین عددی است که روی یال‌های آن مسیر وجود دارد. منظور از **فاصله** دو راس مانند $u$ و $v$ کمینه مقدار وزن تمام مسیرهای ممکن بین $u$ و $v$ است. # ورودی در سطر اول ورودی سه عدد طبیعی $n$ و $m$ و$q$ با فاصله از هم آمده است که به ترتیب نشان دهنده تعداد رئوس، یال‌ها و سوالاتی است که باید به آن‌ها پاسخ بدهیم. $$1 \le n, m, q \le 100\ 000$$ در سطر دوم $n$ عدد مانند $a_1, a_2, a_3,..., a_n$ با فاصله آمده که نشان دهنده اعداد نوشته شده روی رئوس گراف است. در $i$امین سطر از $m$ سطر بعدی، سه عدد $v_i$ و $u_i$ و $w_i$ عدد آمده است که نشان‌دهنده وجود یالی با وزن $w_i$ بین دو راس $v_i$ و $u_i$ است. دقت کنید که لزومی ندارد گراف ساده باشد و ممکن است طوقه یا یال چندگانه داشته باشیم. $$1 \le u_i, v_i \le n$$ $$1 \le w_i \le 10^9 $$ در $j$امین سطر از $q$ سطر بعدی، سه عدد $v_j$ و $x_j$ و $k_j$ آمده است که نشان دهنده سوال علی از شماست؟$$1 \le a_i, x_j \le 500\ 000$$ $$1 \le v_j \le n$$ $$2 \le k_j \le n$$ # خروجی در $q$ سطر خروجی در سطر $i$ام پاسخ سوال $i$ام را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 3 2 6 9 5 1 2 10 2 3 20 1 3 30 3 7 2 1 25 2 ``` ## خروجی نمونه ۱ ``` 20 10 ``` ## ورودی نمونه ۲ ``` 4 3 4 1 2 3 4 1 2 10 2 3 1 3 4 2 3 3 2 4 5 3 4 5 4 1 2 4 ``` ## خروجی نمونه ۲ ``` 2 2 10 -1 ``` # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary>راهنمایی ۱</summary> در ابتدا برای حل مسئله، *mst* گراف را در نظر می‌گیریم. برای این کار از الگوریتم *kruskal* با *dsu* استفاده میکنیم. حال درخت باینری $T$ را بدین‌شکل می‌سازیم که $n$ برگ و $n-1$ غیر برگ داشته باشد و هر برگ آن متناظر یکی از رئوس گراف اولیه و هر غیر برگ آن متناظر یکی از یال های *mst* بوده و دقیقا 2 بچه داشته باشد. اگر در $T$ برگ های هر زیردرخت را بگیریم، در *mst* تشکیل یک زیرگراف همبند می‌دهند که زمانی یکی از مولفه های همبندی *dsu* بوده است. این درخت را همزمان با پیدا کردن *mst* می‌سازیم بدین‌صورت که برای هر مولفه در *dsu* شماره راس ریشه آن را نگه می‌داریم و موقع ادغام کردن دو مولفه، یک راس ریشه جدید ساخته و *parent* ریشه‌های دو مولفه قبلی را راس جدید می‌گذاریم و $value$ راس جدید را هم برابر وزن یال متناظرش در *mst* قرار می‌دهیم. </details> <details class="blue"> <summary>راهنمایی ۲</summary> فرض کنید جعبه‌ای داریم که دو عملیات زیر را در $O(2^6)$ برای دامنه $x$ موجود در صورت مسئله انجام می‌دهد. + `add x` عدد $x$ را به دنباله $A$ اضافه می‌کند. + `get x` تعداد اعضای $A$ که نسبت به $x$ اول هستند را برمی‌گرداند. برای این کار $cnt_x$ را تعریف می‌کنیم را تعداد اعداد $A$ که مضرب $x$ هستند. حال برای پرسش نوع دوم از اصل شمول و عدم شمول استفاده می‌کنیم. به ازای هر مجموعه از عوامل اول $x$ مانند $S$ که ضرب اعضایش $y$ است، مقدار $(-1)^{|S|}*cnt_y$ را به جواب اضافه می‌کنیم. چون همه $x$ ها حداکثر $500\ 000$ اند، پس حداکثر ۶ عامل اول متفاوت دارند و هر درخواست در $O(2^6)$ انجام می‌شود. حال به سوال اصلی باز گردیم. برای جواب دادن کوئری‌های ورودی، می‌توانیم از *Binary Search* روی جواب استفاده کنیم. پاسخ درخواستی که به شکل `v x w` داده می‌شود، تعداد رئوسی است که عدد نوشته شده بر روی آن‌ها، نسبت به $x$ اول است و فاصله‌شان تا $v$ حداکثر $w$است. همچنین می‌دانیم تمام راس‌هایی که شرط فاصله برایشان برقرار است، برگ های یک زیردرخت از $T$ هستند. پس می‌توانیم همه آن‌ها را به جعبه اضافه کرده و در انتها جواب را از جعبه بپرسیم ولی پیچیدگی زمانی این راه بیش از حد مطلوب ماست. </details> <details class="blue"> <summary>راهنمایی ۳</summary> برای بهتر کردن راه قبل میتوان از *Parallel Binary Search* یا باینری سرچ موازی استفاده کرد. میخواهیم همزمان جواب کوئری‌های سوال را حساب کنیم. برای اینکار روی انها همزمان باینری سرچ میزنیم و $O(log(n))$ بار جواب همه کوئری‌ های `v x subtree` را حساب میکنیم. برگ های $T$ را بر حسب *starting time* مرتب کنید. حال هر کویری معادل برگ های یک بازه است که هر کدام معادل دو کویری پریفیکس است. برای جواب دادن کویری های پریفیکس هم برگ ها را به ترتیب به جعبه اضافه کنید و به هر کویری که رسیدید $x$ آن کویری را از جعبه بپرسید. پیچیدگی زمانی: $O((n+q).log(n).2^6)$ </details>