Masala #0273

Sizga \(N\) ta tugundan iborat daraxt berilgan. Daraxtning har bir tugunida nomanfiy qiymat mavjud, bu qiymat shu tugunni bosib o’tish uchun qancha energiya sarflanishini anglatadi. \(\text{Vazn}(A,B)\) deb \(A\) tugundan \(B\) tugunga borish yo’li davomida bosib o’tiladigan (\(A\) va \(B\) tugundan tashqari) barcha tugunlardagi qiymatlar yig’indisiga aytiladi. Sizda daraxt tugunlaridagi qiymatlarni ixtiyoriy nomanfiy qiymatga o’zgartirish imkoniyati bor. Siz \(\sum_{A=1}^{N} \sum_{B=1}^{N} \text{Vazn}(A,B) = 0\) ayniyat to’g’ri bo’lishi uchun kamida nechta tugunning qiymati o’zgartirilishi kerakligini aniqlang.

Kirish faylining dastlabki satrida bitta butun son, \(T(1 \le T \le 10)\) testlar soni kiritiladi.

Har bir test uchun:

Dastlabki satrida bitta butun son, \(N(1 \le N \le 10^5)\) daraxt tugunlari soni kiritiladi.

Keyingi \(N-1\) ta satrda \(U\) va \(V(1 \le U, V \le N,  U \neq V)\) juftliklar kiritiladi, bu juftliklar daraxtning \(U\) va \(V\) tugunlari orasida yo’l mavjuligini ifodalaydi.

Oxirgi qatorda esa \([0, 10^9]\) oralig’idagi \(N\) ta butun son, daraxt tugunlarida keltirilgan qiymatlar.

Har bir test uchun alohida qatorda \(\sum_{A=1}^{N} \sum_{B=1}^{N} \text{Vazn}(A,B) = 0\) ayniyat to’g’ri chiqishi uchun eng kamida nechta tugunning qiymatini nomanfiy butun songa almashtirish kerakligini chop eting