CFR 120 F. Spiders ( Tree Diameter )

Problem - 120F - Codeforces

題意：
給若干顆樹，現在連最少的邊使之連通，求連通後最大直徑。

數據範圍：
樹數量 1 ≤ N ≤ 100
樹大小 2 ≤ s[ i ] ≤ 100

解法：
求直徑總和即可。直徑的找法是，先對一任意一個點，找到其最遠點。該點至它的最遠點的距離即是直徑。

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

int get_dmt( const vvi &G, int u ){
    int t;
    queue< int > que;
    vi vis1( G.size() );
    que.emplace( u );
    vis1[ u ] = 1;
    while( not que.empty() ){
        int x = que.front();
        que.pop();
        t = x;
        for( int y : G[ x ] )
            if( not vis1[ y ] )
                vis1[ y ] = 1,
                que.emplace( y );
    }
    int res = 0;
    queue< pii > q;
    vi vis2( G.size() );
    q.emplace( 0, t );
    vis2[ t ] = 1;
    while( not q.empty() ){
        int d, x; tie( d, x ) = q.front();
        q.pop();
        res = d;
        for( int y : G[ x ] )
            if( not vis2[ y ] )
                vis2[ y ] = 1,
                q.emplace( d + 1, y );
    }
    return res;
}

void solve(){
    freopen( "input.txt", "r", stdin );
    freopen( "output.txt", "w", stdout );
    int N; cin >> N;
    int ans = 0;
    for( int i = 0; i < N; ++i ){
        int s; cin >> s;
        vvi G( s );
        for( int i = 0; i < s - 1; ++i ){
            int u, v; cin >> u >> v; --u, --v;
            G[ u ].emplace_back( v );
            G[ v ].emplace_back( u );
        }
        ans += get_dmt( G, 0 );
    }   
    cout << ans << endl;
}