许诺 • 18天前
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; const int MAXN = 1505; vector tree[MAXN]; int dp[MAXN][2]; bool visited[MAXN]; void dfs(int u) {
visited[u] = true;
dp[u][0] = 0;
dp[u][1] = 1;
for (int v : tree[u]) {
if (!visited[v]) {
dfs(v);
dp[u][0] += dp[v][1];
dp[u][1] += min(dp[v][0], dp[v][1]);
}
}
} int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int id, k;
cin >> id >> k;
for (int j = 0; j < k; j++) {
int r;
cin >> r;
tree[id].push_back(r);
tree[r].push_back(id);
}
}
fill(visited, visited + n, false);
dfs(0);
cout << min(dp[0][0], dp[0][1]) << endl;
return 0;
}
评论:
请先登录,才能进行评论