P2279 [HNOI2003]消防局的设立

#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 1005, M = N << 1;
int n, h[N], e[M], nxt[M], idx;
int f[N][5];
void add(int a, int b) {
	e[++ idx] = b, nxt[idx] = h[a], h[a] = idx;
}
void dfs(int u) {
	f[u][0] = 1;
	for(int i = h[u], v; i; i = nxt[i])
		dfs(v = e[i]), f[u][0] += f[v][4], f[u][3] += f[v][2], f[u][4] += f[v][3];
	if(!h[u]) f[u][1] = f[u][2] = 1;
	else {
		f[u][1] = f[u][2] = 0x3f3f3f3f;
		for(int i = h[u], v; i; i = nxt[i]) {
			v = e[i]; int f0 = f[v][0], f1 = f[v][1];
			for(int j = h[u], k; j; j = nxt[j])
				if(i != j) k = e[j], f0 += f[k][3], f1 += f[k][2];
			f[u][1] = std::min(f[u][1], f0), f[u][2] = std::min(f[u][2], f1);
		}
	}
	for(int i = 1; i <= 4; i ++) f[u][i] = std::min(f[u][i], f[u][i-1]);
}
int main() {
	scanf("%d", &n);
	for(int i = 2, fa; i <= n; i ++)
		scanf("%d", &fa), add(fa, i);
	dfs(1), printf("%d\n", f[1][2]);
	return 0;
}