某岛

… : "…アッカリ~ン . .. . " .. .
March 10, 2020

Luogu P2016. 战略游戏

双倍经验系列。

const int N = int(1e4) + 9;
VI adj[N];
int f0[N], f1[N]; // 放 or 不放, 放
int n, p;

void dfs(int u = 0, int p = -1) {
#define v (*it)
    ECH(it, adj[u]) if (v != p) {
        dfs(v, u);
        f0[u] += f1[v];
        f1[u] += f0[v];
    }
    checkMin(f0[u], f1[u]);
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); REP(i, n) {
        f0[i] = 0; f1[i] = 1;
        int x; RD(x); Rush {
            int y; RD(y);
            adj[x].PB(y);
            adj[y].PB(x);
        }
    }

    dfs();
    cout << f0[0] << endl;
}