比赛 2025暑期集训第4场 评测结果 A
题目名称 战略游戏 最终得分 100
用户昵称 OTTF 运行时间 0.105 s
代码语言 C++ 内存使用 4.02 MiB
提交时间 2025-07-05 09:38:06
显示代码纯文本

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

constexpr int N = 1515;

int n;
vector<int> tree[N];
int dp[N][2];

void dp1 (int now, int dad) {
	int resDo = 0;
	int resDont = 0;
	for (auto son : tree[now]) {
		if (son == dad) {
			continue;
		}
		dp1 (son, now);
		resDo += min (dp[son][0], dp[son][1]);
		resDont += dp[son][1];
	}
	dp[now][1] = 1 + resDo;
	dp[now][0] = resDont;
}

int main () {
	
	freopen ("strategic.in", "r", stdin);
	freopen ("strategic.out", "w", stdout);

	while (cin >> n) {
		for (int i = 1; i <= n; i++) {
			tree[i].clear();
		}

		int u, m, v;
		for (int i = 1; i <= n; i++) {
			scanf ("%d:(%d)", &u, &m);
			u++;
			for (int j = 1; j <= m; j++) {
				scanf ("%d", &v);
				v++;
				tree[u].push_back(v);
				tree[v].push_back(u);
			}
		}

		memset (dp, 0, sizeof (dp));
		dp1 (1, 0);
		cout << min (dp[1][0], dp[1][1]) << endl;
	}
	
	return 0;
}