GCJ 2014 R1A pB. Full Binary Tree ( DFS )

Dashboard - Round 1A 2014 - Google Code Jam
題目中一個合法的完全樹的定義是，所有節點的子節點數為0或2。要求的是移除最少點使得給定的樹成為完全樹。因為數據範圍小，可以考慮枚舉每個節點作為根，再做一次線性的深搜處理。根據定義可以得到遞迴函數，如果一個節點的子節點數為0則花費為0，如果為1則花費為該子樹的節點數總和，如果為2則花費為兩個子樹分別的子問題的花費總和。如果更多，那麼先考慮如果選出兩個子節點 a和 b保留，那麼花費是所有子節點的節點數總和減去 a和 b子樹的節點數總和，再加上 a和 b兩個子問題的花費總和。由於所有子節點的節點數這部分是固定的，所以要找的是最小的兩個 a和 b使得，-( a, b子樹size ) + ( a, b子樹cost )最小。

#include <bits/stdc++.h>
using namespace std;
const int MAXT = 100 + 2;
const int MAXN = 1e3 + 3;

int kase;
int n;
vector< int > G[ MAXN ];

void init( int _n ){
    for( int i = 1; i <= _n; ++i )
        G[ i ].clear();
}

int getSize( int u, int fa ){
    int res = 0;
    for( int v : G[ u ] ){
        if( v == fa ) continue;
        res += getSize( v, u );
    }
    return res + 1;
}

int dfs( int u, int fa ){
    if( G[ u ].size() - ( fa > 0 ) == 0 )
        return 0;
    if( G[ u ].size() - ( fa > 0 ) == 1 ){
        for( int v : G[ u ] ){
            if( v == fa ) continue;
            return getSize( v, u );
        }
    }
    if( G[ u ].size() - ( fa > 0 ) == 2 ){
        int res = 0;
        for( int v : G[ u ] ){
            if( v == fa ) continue;
            res += dfs( v, u );
        }
        return res;
    }
    int sz_sum = 0;
    int min1 = 0, min2 = 0;
    for( int v : G[ u ] ){
        if( v == fa ) continue;
        int v_sz = getSize( v, u );
        int val = -v_sz + dfs( v, u );
        if( val < min1 ){
            min2 = min1;
            min1 = val;
        } else if( val < min2 )
            min2 = val;
        sz_sum += v_sz;
    }
    return sz_sum + min1 + min2;
}

void solve(){
    int ans = n;
    for( int i = 1; i <= n; ++i ){
        ans = min( ans, dfs( i, -1 ) );
        // printf("%d : %d\n", i, dfs( i, -1 ));
    }
    printf("%d\n", ans);
}

int main(){
    int T; scanf("%d", &T);
    for( kase = 1; kase <= T; ++kase ){
        printf("Case #%d: ", kase);
        scanf("%d", &n);
        init( n );
        for( int i = 0; i < n - 1; ++i ){
            int u, v; scanf("%d%d", &u, &v);
            G[ u ].push_back( v );
            G[ v ].push_back( u );
        }
        solve();
    }
    return 0;
}