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

---

کدکاپ سیتی از \(n\) ایستگاه هوایی معلق به نام‌های \(1, 2, \dots, n\) تشکیل شده است. این ایستگاه‌ها با \(n - 1\) پل هوایی به هم متصل هستند و با شروع از هر ایستگاهی می‌توانیم به تمام ایستگاه‌ها با استفاده از پل‌های هوایی برسیم (ساختار ایستگاه‌ها شبیه به درخت است).

می‌دانیم کل شهر کدکاپ در هوا معلق است. در این شهر هر ایستگاه برای معلق ماندن باید به حداقل تعدادی از پل‌های هوایی متصل باشد. عدد سقوط \(f_i\) نشان می‌دهد ایستگاه \(i\) برای معلق ماندن باید به حداقل \(f_i\) پل هوایی متصل باشد.

یک تروریست با خود عهد بسته کاری کند که کل شهر کدکاپ سقوط کند. او قرار است در مرکز کنترل تعدادی از ایستگاه‌ها بمب بگذارد. سپس در لحظه‌ای خاص تمام آن ایستگاه‌ها سقوط خواهند کرد و تمام پل‌های هوایی‌ای که آن‌ها را به ایستگاه های دیگر متصل کرده نیز نابود خواهند شد. سپس تمام ایستگاه‌هایی که با نابودی پل‌ها تعداد پل‌های هوایی متصل به ‌آن‌ها از عدد سقوطشان کمتر شده و دیگر نمی‌توانند معلق بمانند نیز سقوط می‌کنند و دوباره تمام پل‌های هوایی متصل به این ایستگاه‌ها نیز نابود می‌شوند. این روند انقدر تکرار می‌شود تا تمام ایستگاه‌های باقی‌مانده حداقل به اندازه‌ی عدد سقوطشان به پل‌های هوایی متصل باشند.

با توجه به این که امنیت ایستگاه‌ها متفاوت است. تروریست برای بمب‌گذاری هر ایستگاه به اندازه‌ عدد امنیتی آن ایستگاه باید تعدادی سکه رشوه دهد. عدد امنیت ایستگاه \(i\)ام برابر \(s_i\)‌ است. کم‌ترین تعداد سکه‌ای که تروریست نیاز دارد تا بعد از بمب‌گذاری مطمئن باشد تمام ایستگاه‌ها سقوط خواهند کرد چقدر است؟

ورودی

در سطر اول ورودی عدد طبیعی \(t\)، تعداد سناریوها داده می‌شود. \[1 \leq t \leq 100\, 000\] در هر سناریو اطلاعات کامل یک کدکاپ سیتی به صورت زیر به شما داده می‌شود.

در سطر اول هر سناریو عدد طبیعی \(n\) که نشان‌گر تعداد ایستگاه‌ها است به شما داده می‌شود. \[1 \leq n \leq 100\, 000\]

سپس در هر کدام از \(n - 1\) سطر بعدی اطلاعات پل‌های هوایی \(i\)ام داده ‌می‌شود. در هر سطر عدد \(u_i\) و \(v_i\) که نشان‌گر دو ایستگاهی که توسط پل هوایی \(i\)ام به هم متصل‌اند، آمده است.

\[ 1 \leq v_i , u_i \leq n\]

سپس در سطر بعدی \(n\) عدد سقوط ایستگاه‌ها به ترتیب داده می‌شوند. \[ 0 \leq f_i \leq 100\, 000\]

تضمین می‌شود در ابتدا کدکاپ سیتی در هوا معلق است پس عدد سقوط هیچ ایستگاه هوایی‌ای از تعداد پل‌های هوایی متصل به آن بیشتر نیست.

در سطر بعدی به عنوان آخرین سطر ورودی هر سناریو \(n\) اعداد \(s_i\)، نشان‌گر امنیت ایستگاه‌ \(i\)ام به ترتیب داده می‌شوند. \[ 0 \leq s_i \leq 10^9\]

مجموع \(n\)ها در تمام سناریوها حداکثر \(100 \,000\) است. \[1 \leq \sum n \leq 100\, 000\]

خروجی

خروجی شما باید در \(t\) خط داده شود. در هر خط کم‌ترین تعداد سکه‌ای که تروریست برای سقوط کل کدکاپ سیتی نیاز دارد را خروجی دهید.

مثال‌ها

ورودی نمونه ۱

3
3
1 2
2 3
1 1 1
1 1000 2
3
1 2
2 3
1 2 1
1 1000 2
3
1 2
2 3
1 1 1
1 2 3

خروجی نمونه ۱

3
1
2