AC

许诺  •  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;

}


评论:

请先登录,才能进行评论