405 开会

itdef / 2024-10-08 / 原文

// 405 开会.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <cstring>


using namespace std;

/*
http://oj.daimayuan.top/course/5/problem/222

一家公司里有 n个员工，除了公司 CEO 外，每个人都有一个直接上司。公司现在要召开全员大会。
为了充分传递会议信息，每个员工和他/她的直接上司至少得有一个人参加会议。
由于场地限制等原因，现在我们想使得参会人数最少。请问最少需要几个人参会？

输入格式
第一行一个整数n。

接下来一行，n−1个整数f2,f3,…,fn，fi(1≤fi<i)表示第i个员工的上司。其中1号点为CEO，没有上司。

输出格式
一行一个整数，表示答案。

样例输入
5
1 2 3 1
样例输出
2
数据规模
对于所有数据，保证2≤n≤105

2
1
*/

const int N = 100010;
int h[N], e[N], ne[N], idx;
int n;
int dp[N][2];
int ans;

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

void dfs(int u) {
	dp[u][1] = 1;

	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];
		dfs(j);
		dp[u][0] += dp[j][1];
		dp[u][1] += min(dp[j][1], dp[j][0]);
	}

	if (u == 1) {
		ans = min(dp[1][0], dp[1][1]);
	}
}


int main()
{
	memset(h, -1, sizeof h);
	//memset(dp, 0x3f, sizeof dp);
	dp[1][0] = 0x3f3f3f3f;
	cin >> n;
	for (int i = 2; i <= n; i++) {
		int t; cin >> t;
		add(t, i);
	}

	dfs(1);

	cout << ans << endl;
	return 0;
}