UVA 1218 Perfect Service ( 樹DP )

UVa Online Judge
題目大意：N ≤ 1e4 個節點形成一個樹狀結構，求安裝最少的伺服器數量，使得每個不是伺服器的節點恰好和一臺是伺服器的節點相鄰。
由於是樹的結構，我們可以大略閃過一些可能可以當作狀態的字彙，本身是否為伺服器、父節點是否為伺服器。進一步分析，可以分類出
dp( u, 0 )：u節點是伺服器的狀態時的子樹的最少安裝伺服器數量，此時 u的子節點可為伺服器，但不必為
dp( u, 1 )：u節點非伺服器，但 u的父節點是伺服器的狀態，此時 u的子節點必然不為伺服器
dp( u, 2 )：u節點非伺服器，且 u的父節點也非伺服器的狀態，此時 u的子節點裡恰好存在一個伺服器
那麼，可以得出轉移式：
dp( u, 0 ) = sum{ min{ dp( v, 0 ) + dp( v, 1 ) } } + 1 | Ɐ v is son of u
dp( u, 1 ) = sum{ dp( v, 2 ) } | Ɐ v is son of u
dp( u, 2 ) = min{ dp( u, 1 ) - dp( v, 2 ) + dp( v, 0 ) } | Ɐ v is son of u
其中第三個轉移是比較不好想到，需要一些靈感。。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
const int INF = MAXN;

int n;
vector<int> e[MAXN];

int memo[MAXN][3];
int dp(int u, int s, int fa){
    if( memo[u][s] != -1 ) return memo[u][s];
    if( s == 0 ){ // u is server
        memo[u][s] = 1;
        for(int i = 0; i < e[u].size(); ++i)
            if( e[u][i] != fa )
                memo[u][s] += min( dp( e[u][i], 0, u ), dp( e[u][i], 1, u ) );
    } else if( s == 1 ){ // u is not server but fa[u] is server
        memo[u][s] = 0;
        for(int i = 0; i < e[u].size(); ++i)
            if( e[u][i] != fa )
                memo[u][s] += dp( e[u][i], 2, u );
    } else{ // otherwise, the case is to be neither u nor fa[u] is server
        memo[u][s] = INF;
        for(int i = 0; i < e[u].size(); ++i)
            if( e[u][i] != fa )
                memo[u][s] = min( memo[u][s], 
                        dp( u, 1, fa ) - dp( e[u][i], 2, u ) + dp( e[u][i], 0, u ) );
    }
    return memo[u][s];
}

int main(){
    ios::sync_with_stdio(false);
    while( cin >> n ){
        for(int i = 0; i < MAXN; ++i) e[i].clear();
        for(int i = 0; i < n - 1; ++i){
            int a, b; cin >> a >> b;
            e[a].push_back( b );
            e[b].push_back( a );
        } int z; cin >> z; // useless
        memset( memo, -1, sizeof(memo) );
        cout << min( dp( 1, 0, -1 ), dp( 1, 2, -1 ) ) << endl;
    }
    return 0;
}