略。）

const int N = 10009;

int dp0[N], dp1[N], dp2[N];

VI adj[N]; bool vst[N];
int n;

void dfs(int u = 0){
    vst[u] = true; int delta = INF; dp0[u] = 1;

#define v adj[u][i]

    REP(i, SZ(adj[u])) if (!vst[v]){
        dfs(v), dp0[u] += min(dp0[v], dp1[v], dp2[v]), dp2[u] += dp1[v];
        if (dp0[v] <= dp1[v]) dp1[u] += dp0[v], delta = 0;
        else dp1[u] += dp1[v], checkMin(delta, dp0[v] - dp1[v]);;
    }

    dp1[u] += delta;
}

int main(){
    int a, b; FOR_C(i, 1, _RD(n)) RD(a, b), --a, --b, adj[a].PB(b), adj[b].PB(a);
    dfs(), OT(min(dp0[0], dp1[0]));
}

Posted by xiaodao
Category: POJ