logu P2016

// Problem: P2016 战略游戏
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2016
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using vl = vector<ll>;
using vi = vector<int>;

int n;
vi g[2048];

pii dfs(int u, int pa)
{
    pii ans = {1, 0};
    for (auto v : g[u]) {
        if (v == pa)
            continue;
        auto [place, no_place] = dfs(v, u);
        ans.first += min(place, no_place);
        ans.second += place;
    }
    return ans;
}
pii dfs1(int u, int pa)
{
    int all = 0;
    int min_delta = INT_MAX / 2;
    for (auto v : g[u]) {
        if (v == pa)
            continue;
        auto [sw, swn] = dfs(v, u);
        all += min(sw, swn);
        min_delta = min(min_delta, sw - swn);
    }
    return {all + 1, all + (min_delta > 0 ? min_delta : 0)};
}

int main(int argc, char **argv)
{
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int u, v, k;
        cin >> u >> k;
        for (int j = 0; j < k; ++j) {
            cin >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }
    auto ret = dfs(0, -1);
    dbg(ret.first, ret.second);
    cout << min(ret.first, ret.second) << endl;
    return 0;
};