물탱크 알바(Hard)

이 문제는 물탱크 알바(Easy)의 상위 문제이고, 물탱크 알바(Easy)에 이 문제의 정답 코드를 제출하여 맞힐 수 있다.

잔나비 콘서트에 가기 위한 돈을 벌려고 창연이는 송도수자원공사에 취직했다.

송도수자원공사의 정수 시설은 물탱크 $n$개와 물탱크를 연결하는 수로 $n-1$개로 구성된다. 정수 시설은 $1$번 물탱크를 루트로 하는 이진 트리이며, $i$번 물탱크의 용량은 $c_i$다. 창연이는 임의의 물탱크 하나에 펌프를 연결하여 $m$의 물을 흘려보낼 수 있다.

왼쪽 그림은 $1$번 물탱크에 $3$의 물을 넣은 결과이고, 오른쪽 그림은 $2$번 물탱크에 $3$의 물을 넣은 결과이다.

물탱크에 흘러든 물은 다음과 같이 움직인다. 편의를 위해 수로에는 용량이 없다고 가정한다.

• 바로 아래에 직접 연결된 물탱크 중 꽉 차지 않은 물탱크가 1개만 있다면, 흘러 들어온 물은 그 물탱크로 고스란히 흘러 내려간다.
• 바로 아래에 직접 연결된 물탱크 중 꽉 차지 않은 물탱크가 2개 있다면, 흘러 들어온 물은 절반씩 나뉘어 두 물탱크로 흘러 내려간다.
• 바로 아래에 직접 연결된 물탱크 중 꽉 차지 않은 물탱크가 없고 현재 물탱크가 꽉 차지 않았다면, 흘러 들어온 물은 현재 물탱크에 차오른다.
• 바로 아래에 직접 연결된 물탱크 중 꽉 차지 않은 물탱크가 없고 현재 물탱크가 꽉 찼다면, 물은 흘러 들어오지 않고 그대로 부모 물탱크로 넘쳐 올라간다.

송도수자원공사는 정수 능력에 비례하여 일당을 주고, 정수 시설의 정수 능력은 꽉 찬 물탱크 수에 비례한다.

창연이가 빠르게 콘서트비를 마련할 수 있도록 도와주자!

첫 번째 줄에는 두 정수 $n$, $m$이 공백으로 구분되어 주어진다.

두 번째 줄에는 $n$개의 정수 $c_1,c_2,\ldots ,c_n$이 공백으로 구분되어 주어진다.

세 번째 줄에는 $n-1$개의 정수 $p_2,p_3,\ldots ,p_n$이 공백으로 구분되어 주어진다. $p_i$는 $i$번 물탱크의 부모 물탱크 번호이다.

임의의 물탱크 하나에 펌프를 연결하여 $m$의 물을 흘려보내서 꽉 채울 수 있는 물탱크 수의 최댓값을 출력한다.

• $2\le n\le 200\,000$.
• $1\le c_i\le 10^9$.
• $1\le m\le c_1+c_2+\cdots +c_n$.
• $1\le p_i\le i-1$.
• 물탱크의 구조는 루트가 $1$인 이진 트리임이 보장된다.