Masala #0273
Yo’l vazni
Sizga ta tugundan iborat daraxt berilgan. Daraxtning har bir tugunida nomanfiy qiymat mavjud, bu qiymat shu tugunni bosib o’tish uchun qancha energiya sarflanishini anglatadi. deb tugundan tugunga borish yo’li davomida bosib o’tiladigan ( va tugundan tashqari) barcha tugunlardagi qiymatlar yig’indisiga aytiladi. Sizda daraxt tugunlaridagi qiymatlarni ixtiyoriy nomanfiy qiymatga o’zgartirish imkoniyati bor. Siz ayniyat to’g’ri bo’lishi uchun kamida nechta tugunning qiymati o’zgartirilishi kerakligini aniqlang.
Kirish faylining dastlabki satrida bitta butun son, testlar soni kiritiladi.
Har bir test uchun:
Dastlabki satrida bitta butun son, daraxt tugunlari soni kiritiladi.
Keyingi ta satrda va juftliklar kiritiladi, bu juftliklar daraxtning va tugunlari orasida yo’l mavjuligini ifodalaydi.
Oxirgi qatorda esa oralig’idagi ta butun son, daraxt tugunlarida keltirilgan qiymatlar.
Har bir test uchun alohida qatorda ayniyat to’g’ri chiqishi uchun eng kamida nechta tugunning qiymatini nomanfiy butun songa almashtirish kerakligini chop eting
# | input.txt | output.txt |
---|---|---|
1 |
1 3 1 2 1 3 1 2 3 |
1 |