Nüsxələrin düzülüşü
Topskiy informasiyanın çatdırılması üçün şəbəkə qurmaq istəyir. Şəbəkə şəkildə göstərildiyi kimi cari server və bir neçə güzgü serverindən təşkil olunur. Giriş verilənləri başlanğıc serverdə yerləşir (şəkil 1-də kökdə), eyni zamanda onların nüsxələri bəzi güzgü serverlərə çatdırılır (şəkil 1-də 2 və 5 təpələri). Qovşaq verilənlərin axtarılması üçün sorğu göndərən zaman, o verilənləri növbəti yerlərdə tapmağa çalışır.
Qovşaqda verilənlərin nüsxəsinin olmasını yoxlayırıq. Əgər belədirsə, sorğu yerinə yetirilmişdir. Əks halda 2-ci addıma keçirik.
Sorğunu 1-ci addımın həyata keçirdiyi valideynə veririk.
C(v) sorğusunun icrasının qiyməti yoldakı tillərin çəkilərinin cəmi kimi təyin edilir. Əgər C(v) Q(v)-nin üst sərhəddindən böyük deyilsə, onda axtarışın qiyməti qəbul olunmuş sayılır. Topskiy v təpəsində verilənlər yazısında mənfi olmayan S(v) qiymətinin olmasını ehtimal edir. Cari server xüsusidir, onda verilənlərin saxlanılması qiyməti 0-dır. Topskiy verilənlərin nüsxəsini serverdə elə yerləşdirmək istəyir ki, bütün təpələrin axtarış qiyməti münasib olsun, verilənlər yazısının ümumi qiyməti ən az olsun.
Giriş verilənləri
İlk sətir testlərin t (t ≤ 20) sayını ehtiva edir. Hər bir test serverlərin sayını ifadə edən n (1 ≤ n ≤ 1000) tam ədədi ilə başlayır. Sonra hər biri 4 tam F_v (0 ≤ F_v ≤ n), Q_v, S_v və W_v (0 ≤ Q_v, S_v, W_v ≤ 10^5) ədədlərini ehtiva edən n sətir verilir. i (1 ≤ i ≤ n) sətrindəki F_v i təpəsinin atasını ifadə edir (əgər F_v 0-a bərabərdirsə, inda i cari server sayılır, Q_v -1-ə bərabərdirsə, S_v və W_v 0-a bərabərdir), Q_v axtarış qiymətinin üst sərhəddidir. S_v i təpəsindəki verilənlər yazısının qiymətinə bərabərdir, W_v isə i və F_v təpələrini birləşdirən tilin çəkisinə bərabərdir.
Çıxış verilənləri
Hər bir test üçün ayrı sətirdə verilənlərin saxlanılması üçün məsrəfin minimal qiymətini verməli.