Antivirus#13068

Antivirus

1,5 saniyə
256 meqabayt

Ostapın kompüterində -dən -ə qədər nömrələnmiş qovluq var. nömrəli qovluq kökdür, hər digər qovluğu (2 \le i \le n) isə birbaşa a_i qovluğunun içində yerləşir; zəmanət verilir ki, a_i < i.

Ostap antivirusu dəfə işə salıb. -ci işə salma c_j qovluğunu və onun içində yerləşən, c_j-dən d_j səviyyədən dərin olmayan bütün qovluqları yoxlayır.

Formal olaraq, qovluğu -ci işə salma tərəfindən yoxlanılır, əgər c_j-dən başlayaraq qovluqdan birbaşa onun içində yerləşən qovluğa keçməklə ən çoxu d_j dəfəyə -yə çatmaq mümkündürsə. Xüsusilə, d_j = 0 olduqda belə, c_j qovluğu həmişə -ci işə salma tərəfindən yoxlanılır.

Eyni qovluq bir neçə dəfə yoxlanıla bilərdi. Ən azı bir işə salma tərəfindən yoxlanılan qovluqların sayını tapın.

Giriş

Birinci sətirdə iki tam ədəd və (2 \le n \le 3 \cdot 10^5, 1 \le k \le 3 \cdot 10^5) verilir — qovluqların sayı və antivirusun işə salınmalarının sayı.

İkinci sətirdə n - 1 tam ədəd a_2, a_3, \ldots, a_n (1 \le a_i < i) verilir, burada a_i — qovluğunun yaradıldığı qovluqdur.

Sonrakı sətirin hər birində iki tam ədəd c_j və d_j (1 \le c_j \le n, 0 \le d_j \le 3 \cdot 10^5) verilir — -ci işə salmanın qovluğu və dərinliyi.

Çıxış

Bir tam ədəd çıxarın — ən azı bir işə salma tərəfindən yoxlanılan qovluqların sayı.

Nümunələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Qeyd

Birinci nümunədə qovluğu və qovluqlarını, qovluğu və qovluqlarını, qovluğu qovluğunu, qovluğu isə və qovluqlarını ehtiva edir. Birinci işə salma , və qovluqlarını yoxlayır (mavi rəng); ikincisi yalnız qovluğunu yoxlayır (yaşıl rəng); üçüncüsü yalnız qovluğunu yoxlayır (qırmızı rəng), çünki onun içində başqa qovluq yoxdur. Ümumilikdə qovluq yoxlanılır.

İkinci nümunədə birinci işə salma , , və qovluqlarını, ikincisi qovluğunu, üçüncüsü qovluğunu, dördüncüsü isə qovluğunu yoxlayır. qovluğu yoxlanılmır, buna görə də cavab -dir.