- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ثنا پس از ماجراجویی‌های ویتنام در جنگل‌های ویتنام گم شده است و GPS او از کار افتاده است. نقشه‌ی ویتنام به صورت یک درخت وزن‌دار با $n$ رأس مدل می‌شود؛ هر یال وزن مثبتی دارد و فاصله‌ی بین دو رأس برابر است با مجموع وزن یال‌های مسیر یکتا بین آن دو رأس. ثنا می‌داند که در یکی از رئوس این درخت قرار دارد.
او با استفاده از دانش خود در زمینه‌ی سیگنال‌ها دستگاهی ساخته که می‌تواند به برج‌های مخابراتی راس‌های مختلف وصل شود. هر بار که سیگنالی دریافت می‌کند، با توجه به زمان رفت‌وبرگشت سیگنال نتیجه می‌گیرد که فاصله‌ی راسی که در آن قرار دارد تا یک رأس مشخص، از مقداری معین بیشتر نیست.
حالا ثنا می‌خواهد برنامه‌ای بنویسد تا با تحلیل این داده‌ها مکان خود را شناسایی کند. باید $q$ کوئری را پردازش کنید. در هر کوئری یا سیگنال جدیدی دریافت می‌شود. یا صدرا (برادر کوچک ثنا که طاقتش طاق شده) از او می‌پرسد که آیا با توجه به اطلاعاتی که تا به حال دریافت کرده ممکن است در راس $v$ باشیم یا خیر. دو نوع کوئری داریم:
- 1 v x :
از این لحظه به بعد می‌دانیم فاصله تا راس $v$ حداکثر $x$ است.
- 2 v :
باید به این پرسش پاسخ دهید که آیا ممکن است در راس $v$ باشیم یا نه.
ممکن است هیچ یک از رئوس در اطلاعات دریافت شده صدق نکند. به نمونه‌ی اول توجه کنید.
ورودی
در خط اول ورودی تعداد تست‌کیس‌ها $T$ می‌آید.
در خط اول هر تست‌کیس عدد $n$، تعداد رئوس درخت می‌آید.
در $n - 1$ خب بعدی توصیف یال‌های درخت می‌آید. در هر خط به ترتیب سه عدد $v_i u_i w_i$ که به معنی وجود یک یال به وزن $w_i$ بین رئوس $v_i$ و $u_i$ است.
در خط بعدی عدد $q$، تعداد کوئری‌ها می‌آید. در هر یک از $q$ خط بعدی یک کوئری به یکی از دو فرمت زیر می‌آید:
- 1 v x
- 2 v
خروجی
به ازای هر کوئری از نوع دوم، در یک خط چاپ کنید Yes اگر ممکن است ثنا در آن راس باشد، و No اگر ممکن نیست.
محدودیت‌ها
$$ 1 \leq T \leq 10^5 $$$$ 1 \leq n \leq 2 \cdot 10^5 $$$$ 1 \leq w_i \leq 1000 $$ $$ 1 \leq q \leq 4 \cdot 10^5 $$$$ 1 \leq v \leq n $$$$ 1 \leq x \leq 10^9 $$
- تضمین می‌شود دنباله‌ی ورودی یک درخت را توصیف می‌کند.
$$ \sum n \leq 2 \cdot 10^5 $$ $$ \sum q \leq 4 \cdot 10^5 $$
مثال
2
3
1 2 2
1 3 2
6
1 1 2
2 2
1 1 1
2 2
1 2 0
2 1
6
1 2 262
1 3 396
2 6 724
3 4 693
4 5 845
9
1 5 2501
2 6
2 5
1 3 1273
2 5
1 1 372
1 6 871
2 3
2 2
Yes
No
No
No
Yes
No
No
Yes
ارسال پاسخ برای این سؤال