32225번 - 물탱크 알바(Hard)

문제

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

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

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

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

• 자신의 아래쪽으로 직접 연결된 물탱크 중 꽉 차지 않은 물탱크가 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ドル$인 이진트리임이 보장된다.

힌트