CFR 734 E. Anton and Tree ( Ad hoc, Tree )

題意：
給一棵樹，每個節點有顏色，黑或白。每次可以選一個同顏色的連通分量，將全部顏色反轉。求最少反轉次數，使得樹的所有節點同色。

資料規模：
節點數 1 ≤ N ≤ 2e5

解法：
先對原圖做連通分量縮點去想。如果用連通分量個數變化的角度思考，會發現需要做枚舉，那樣複雜度會很糟糕。但如果用邊數的變化，進一步想到直徑的變化，便會發現每次至多可以讓直徑減少 2 ( 除非只剩兩個點 )，而當直徑為 0 的時候滿足所有節點同色。同時，除非只剩兩個點，每次都能將當前直徑減少 2，因此答案為原圖連通分量縮點後的直徑除以二，向上取整。

時間 / 空間複雜度：
O( N )

int N;
vi C;
vvi G;

void init(){
    cin >> N;
    C = vi( N );
    for( int i = 0; i < N; ++i )
        cin >> C[ i ];
    G = vvi( N );
    for( int i = 0; i < N - 1; ++i ){
        int u, v; cin >> u >> v; --u, --v;
        G[ u ].emplace_back( v );
        G[ v ].emplace_back( u );
    }
}

void solve(){
    vi vis( N );
    int far1;
    queue< int > que;
    que.emplace( 0 );
    vis[ 0 ] = 1;
    while( not que.empty() ){
        int u = que.front();
        que.pop();
        far1 = u;
        queue< int > q;
        q.emplace( u );
        while( not q.empty() ){
            int v = q.front();
            q.pop();
            for( int x : G[ v ] ){
                if( vis[ x ] ) continue;
                vis[ x ] = 1;
                if( C[ v ] == C[ x ] )
                    q.emplace( x );
                else
                    que.emplace( x );
            }
        }
    }
    vis = vi( N );
    int dmt;
    queue< pii > d_u;
    d_u.emplace( 0, far1 );
    vis[ far1 ] = 1;
    while( not d_u.empty() ){
        int d, u; tie( d, u ) = d_u.front();
        d_u.pop();
        dmt = d;
        queue< int > q;
        q.emplace( u );
        while( not q.empty() ){
            int v = q.front();
            q.pop();
            for( int x : G[ v ] ){
                if( vis[ x ] ) continue;
                vis[ x ] = 1;
                if( C[ v ] == C[ x ] )
                    q.emplace( x );
                else
                    d_u.emplace( d + 1, x );
            }
        }
    }
    cout << ( dmt + 1 >> 1 ) << endl;
}