Nüsxələrin düzülüşü#2189
Topsky məzmun çatdırılma şəbəkəsi qurmaq istəyir. Bu şəbəkə orijin server və bir neçə güzgü (mirror) serverindən ibarətdir, şəkildə (1) göstərildiyi kimi. Orijinal məlumat orijin serverində (şəkildə kök qovşaq — 1) saxlanılır, kopyalar isə bəzi güzgü serverlərində yerləşdirilə bilər (şəkildə qovşaqlar 2 və 5). Hər hansı bir qovşaq məlumat tələb etdikdə, aşağıdakı qaydada onu axtarır.
Əgər öz yerləşdiyi yerdə kopya varsa, sorğu təmin olunur. Əks halda, 2-ci mərhələyə keç.
Sorğunu öz valideyninə ötür və valideyn qovşaq 1-ci addımı həyata keçirsin.
Sorğunu yerinə yetirmə xərcinə C(v) deyilir və bu, yol boyunca olan kənarların çəkilərinin cəminə bərabərdir. Əgər C(v) yuxarı həddi Q(v) aşmırsa, o zaman sorğunun alınması xərci qənaətbəxş sayılır. Topsky həmçinin qeyri-mənfi saxlama xərci S(v) olduğunu düşünür; bu, məlumatın v qovşağında saxlanma xərcləridir. Qeyd edək ki, orijin server istisnadır: orijin server üçün saxlama xərci 0-dır.
Topsky istəyir ki, kopyalar elə yerləşdirilsin ki, bütün qovşaqlar üçün sorğunu yerinə yetirmə xərci qənaətbəxş olsun və ümumi saxlama xərci minimum olsun.
Birinci sətirdə testlərin sayı t (1 \leq t \leq 20) verilir. Hər testdə əvvəlcə serverlərin sayı n (1 \leq n \leq 1000) verilir. Sonra n sətir ard-arda gəlir. Hər sətirdə dörd tam ədəd var: F_v (0 \leq F_v \leq n), Q_v, S_v, və W_v (0 \leq Q_v, S_v, W_v \leq 10^5). i-ci sətirdə (1 \leq i \leq n), F_v i-ci qovşağın valideynini göstərir (əgər F_v -dırsa, onda i-ci qovşaq orijin serverdir və bu qovşaq üçün Q_v, S_v, W_v dəyərləri müvafiq olaraq , , olur); Q_v alınması üçün yuxarı həddi, S_v i-ci qovşaqda məlumatı saxlama xərcini, və W_v isə i-ci qovşaqla F_v arasındakı kənarın çəkisini göstərir.
Hər test üçün cavabı — minimal ümumi saxlama xərcini ayrıca sətirdə çap edin.
Nümunə 1