Banja i Voža su se konačno obogatili. Vlasnici su korporacije Makrohard koja se u poslednje vreme pokazala kao neprikosnoveno najbolja u polju razvoja operativnih sistema i internet servisa. Makrohard je organizovan u vidu n poslovnica koje se nalaze u strogoj hijerarhiji. Poslovnica 1 je sedište korporacije i ona je, direktno ili indirektno (preko drugih poslovnica), nadređena svim ostalim. Svaka druga poslovnica ima tačno jednu direktno nadrešenu koja ima redni broj manji od nje. Vrednosti svih poslovnica su zadate u milionima dolara.

Na žalost, kako to obično biva, Banja i Voža su se posvašali oko dizajna zvanične šolje za kafu korporacije i odlučili da više ne mogu da posluju zajedno. Srećom, njihova dugogodišnja poznanica, a sada kontroverzni biznismen, Tana Rišović odlučila je da kupi Makrohard i tako pomogne Banji i Voži da se rastanu pre nego što dođe do većih incidenata. Međutim, svi znamo da milionske transakcije nikada nisu jednostavne i da ih, ukoliko ne želimo da veliki deo novca završi u rukama Poreske uprave, moramo pažljivo planirati.

Tanin računovođa je zaključio da, kako bi ukupan porez bio što manji, Tana svakog meseca treba da kupi tačno jednu poslovnicu Makroharda zajedno sa svim ostalim kojima je ona nadređena (direktno ili indirektno) a koje već ne poseduje, i pritom potroši najviše k miliona dolara. Vaš zadatak je da pomognete Tani tako što ćete izračunati minimalno trajanje ove transakcije.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke porez.in.) U prvom redu ulazne datoteke nalaze se prirodni brojevi n (1 ≤ n ≤ 100.000) i k (1 ≤ k ≤ 2³⁰) - broj poslovnica firme Makrohard i količina novca koju Tana može da potroši svakog meseca. U sledećem redu nalazi se n prirodnih brojeva razdvojenih razmacima - qlanovi niza V , gde V_i predstavlja vrednost svake od poslovnica u milionima dolara (V_i ≤ 2³⁰). U trećem redu nalazi se n - 1 prirodan broj - članovi niza A, gde A_i predstavlja redni broj direktno nadređene poslovnice za poslovnicu i + 1 (A_i ≤ i).

Izlaz.

(Izlazni podaci se ispisuju u datoteku porez.out) U prvom i jedinom redu izlazne datoteke ispisati jedan ceo broj - najmanji broj mesečnih transakcija potreban da bi se prodaja Makroharda okončala.

Primer 1.

6 20
7 6 7 5 6 4
1 1 2 4 4

2

Objašnjenje.Tana će u prvom mesecu kupiti poslovnice 4,5 i 6, a u drugom 1,2 i 3.

Napomena. Transakcija će uvek moći da se obavi.

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int n,k;
int mint[100000]; //najmanji broj kupovina za podstablo sa korenom i
int minr[100000]; //minimalna vrednost pri poslednjoj kupovini za mint[i]
int v[100000];
int nad[100000];
vector <int> potomak[100000]; //potomci cvora i
bool cmp (int a,int b) { return minr[a]<minr[b]; }
int main ()
{
    freopen("porez.in","r",stdin);
    freopen("porez.out","w",stdout);
    scanf("%d %d",&n,&k);
    for (int i=0;i<n;i++) scanf("%d",&v[i]);
    for (int i=1;i<n;i++) {scanf("%d",&nad[i]);nad[i]--;potomak[nad[i]].push_back(i);}
    for (int i=n-1;i>=0;i--)
    {
        int t=1;
        int r=v[i];
        sort(potomak[i].begin(),potomak[i].end(),cmp);
        for (int j=0;j<potomak[i].size();j++)
        {
            t+=mint[potomak[i][j]];
            if (r+minr[potomak[i][j]] <= k)
            {
                r+=minr[potomak[i][j]];
                t--;
            }
        }
        mint[i]=t;
        minr[i]=r;
    }
    printf("%d\n",mint[0]);
}