CFR 238 1C. World Eater Brothers ( Tree DP )

Problem - C - Codeforces
基本上和這道題是相同的概念
CFR 219 D. Choosing Capital for Treeland ( Tree DP ) - 0w1
不過這題的要點在於意識到樹的唯一路徑性質使得選擇任一條邊後兩端一定可以各自形成一顆子樹。因此只要枚舉所有邊，再各自處理所有情況就行了。
但還是WA了一次，沒注意到城市數量可以是1，太陰險了哈哈哈。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e3 + 3;
typedef pair< int, int > pii;

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

int dfs1( int u, int fa ){
    int res = 0;
    for( pii &p : G[ u ] ){
        int v = p.first;
        int w = p.second;
        if( v == fa ) continue;
        res += dfs1( v, u ) + ( w == 1 ? 0 : 1 );
    }
    return res;
}

int dp[ MAXN ];
void dfs2( int u, int fa, int ucost ){
    dp[ u ] = ucost;
    for( pii &p : G[ u ] ){
        int v = p.first;
        int w = p.second;
        if( v == fa ) continue;
        dfs2( v, u, ucost + w );
    }
}

int subsolve( int u, int fa ){
    int ucost = dfs1( u, fa );
    memset( dp, 0x3f3f3f3f, sizeof(dp) );
    dfs2( u, fa, ucost );
    return *min_element( dp, dp + MAXN );
}

void solve(){
    if( n == 1 ) return (void)puts("0");
    int ans = 1e9;
    for( int u = 1; u <= n; ++u )
        for( pii &p : G[ u ] ){
            int v = p.first;
            int w = p.second;
            if( w == -1 ) continue;
            ans = min( ans, subsolve( u, v ) + subsolve( v, u ) );
        }
    printf("%d\n", ans);
}

int main(){
    scanf("%d", &n);
    for( int i = 0; i < n - 1; ++i ){
        int u, v; scanf("%d%d", &u, &v);
        G[ u ].push_back( pii( v, 1 ) );
        G[ v ].push_back( pii( u, -1 ) );
    }
    solve();
    return 0;
}