CFR 219 D. Choosing Capital for Treeland ( Tree DP )

Problem - D - Codeforces
搞了很久才弄出來。。首先要分成兩種邊，一種是順向邊，輸入給定的邊，一種是逆向邊，就是要經過反轉才能用的邊。這麼一來，我們可以先透過一次深搜得到隨便一個點當根的時候的花費。顯然我們不能暴力對所有根重新計算，但我們可以試著思考能不能由別的根的答案遞推出當前的根的答案。可以發現，只要從頭到尾都固定一個有根樹的形狀，那麼把根轉移到當前根的一個子節點時變化的花費其實是只有那一個轉移邊而已。如果轉移邊是指向新的根，那麼就要將它反轉所以花費加一，否則就不需要反轉，但會被上一次的狀態計入所以減一。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
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 == 1 ? 0 : 1 );
        if( v == fa ) continue;
        res += w + dfs1( v, u );
    }
    return res;
}

int cost[ MAXN ];

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

void solve(){
    cost[ 1 ] = dfs1( 1, -1 );
    dfs2( 1, -1, cost[ 1 ] );
    int minv = 1e9;
    for( int i = 1; i <= n; ++i )
        minv = min( minv, cost[ i ] );
    printf("%d\n", minv);
    vector< int > ans;
    for( int i = 1; i <= n; ++i )
        if( minv == cost[ i ] )
            ans.push_back( i );
    for( int i = 0; i < ans.size(); ++i )
        printf("%d%c", ans[ i ], i == ans.size() - 1 ? '\n' : ' ');
}

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;
}