لشکر کشی نادرشاه


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

نادرشاه قصد لشکر کشی به کل دنیا برای فتح غنائم را دارد. هر کشور قابل نمایش به صورت یک گراف درخت است که در آن شهرها رئوس گراف و راه بین شهرها یال‌های درخت است. در هر شهر مثل vv تعداد CvC_v الماس وجود دارد که اگر لشکری از نادرشاه به آن شهر برسد همه الماس‌های آن را غارت می‌کند.

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

توجه کنید ممکن است به یک شهر چند لشکر حمله کنند ولی اولا تنها یکبار الماس‌های آن غارت می‌شود و ثانیا هیچ لشکری دوبار به آن حمله نمی‌کند.

مسلما نادرشاه آنقدر باهوش هست که نیاز به کمک شما در استراتژی حمله نداشته باشد. به تاریخ‌دانان بگویید نادر چه تعداد الماس از هر جنگ غارت کرده!

ورودی🔗

در سطر اول ورودی tt تعداد کشورهای مورد هجوم نادرشاه می‌آید و سپس اطلاعات tt کشور می‌آید. 1t194 1 \le t \le 194 در سطر اول برای کشور ii به ترتیب سه عدد صحیح با فاصله می‌آید که عدد اول نشانگر تعداد شهر NiN_i، عدد دوم شهر ورودی لشکرها IiI_i و عدد سوم تعداد لشکرهای نادرشاه AiA_i است. 1Ii,AiNi 1 \le I_i, A_i \le N_i i=1tNi100000 \sum_{i=1}^t N_i \le 100 \, 000 i=1tAi2000 \sum_{i=1}^t A_i \le 2000 سپس در سطر بعد NiN_i عدد با فاصله می‌آید که jjمین عدد نشانگر CjiC_{j_i} تعداد الماس‌های شهر jj در کشور ii است. 0Cji10000 0 \le C_{j_i} \le 10 \, 000 سپس در Ni1N_i - 1 سطر بعد در هر سطر دو عدد uiu_i و viv_i می‌آید که نشان می‌دهد شهر uu و vv در کشور ii به هم متصل هستند. 1ui,viNi 1 \le u_i, v_i \le N_i

خروجی🔗

در سطر ii از tt سطر خروجی حداکثر تعداد الماس‌های ممکن از غارت کشور ii را بنویسید.

مثال🔗

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

3
5 3 2
1 2 3 4 5
1 3
3 2
4 3
3 5
5 1 2
1 0 3 1 1
1 2
1 3
3 4
3 5
3 1 2
0 25 75
1 2
2 3
Plain text

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

12
6
100
Plain text