1153D - Serval and Rooted Tree - CodeForces Solution

//dp[i]:if Max v is w, then need w + dp[i]
#include <iostream>
#include <cstring>

using namespace std;

const int N = 3e5 + 10; 

int n, leaf;
int fa[N], dp[N], m[N];
int h[N], e[N], ne[N], idx;

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void dfs(int x) {
	for (int i = h[x]; ~i; i = ne[i]) {
		int j = e[i];
		dfs(j);
	}
	if (h[x] == -1) dp[x] = 0, leaf ++;
	else {
		if (m[x]) {
			dp[x] = 998244353;
			for (int i = h[x]; ~i; i = ne[i]) dp[x] = min(dp[x], dp[e[i]]);
		}
		else {
			for (int i = h[x]; ~i; i = ne[i]) dp[x] += dp[e[i]] + 1;
			dp[x] --;
		}
	}
}

int main() {
	memset(h, -1, sizeof h);
	
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i ++) scanf("%d", &m[i]);
	
	for (int i = 2; i <= n; i ++) {
		scanf("%d", &fa[i]);
		add(fa[i], i);
	}
	
	dfs(1);
	
	printf("%d", leaf - dp[1]);
	
	return 0;
}