CFR 342 E. Xenia and Tree ( LCA + Square Decompostion )

Problem - E - Codeforces
如果對於一個詢問，對所有塗色點取最小距離，複雜度為O( N )，如果對於一個添加所有點的答案，複雜度為O( N )。又只要開始的時候將所有始點押入 queue，囤積複數個始點再更新所有點的答案的複雜度依然為O( N )，可以考慮平方分割。對於一個新的添加，不馬上利用它更新答案而是押入一個集合，令集合最大容量為 B，當集合大小超過 B，集合裡的所有點押入 queue立刻更新。對於一個詢問，取已更新的答案和對未更新的點一一取最小距離判斷。複雜度為 O( N * M / B + B * lg( N ) * M )。

#include <bits/stdc++.h>
using namespace std;

typedef vector< int > vi;
typedef vector< vi > vvi;

const int BSIZE = 77;

void fillTable( int u, int fa, int lv, const vvi &G, vi &depth, vvi &par ){
    depth[ u ] = lv;
    for( int v : G[ u ] ){
        if( v == fa ) continue;
        fillTable( v, u, lv + 1, G, depth, par );
        par[ 0 ][ v ] = u;
    }
}

int getLCA( int u, int v, const vi &depth, const vvi &par ){
    if( not ( depth[ u ] > depth[ v ] ) )
        swap( u, v );

    int diff = depth[ u ] - depth[ v ];
    for( int i = 19; diff; --i )
        if( diff >= 1 << i )
            u = par[ i ][ u ],
            diff -= 1 << i;

    if( u == v ) return u;

    for( int i = 19; par[ 0 ][ u ] != par[ 0 ][ v ]; --i )
        if( par[ i ][ u ] != par[ i ][ v ] )
            u = par[ i ][ u ],
            v = par[ i ][ v ];

    return par[ 0 ][ u ];
}

int getDis( int u, int v, const vi &depth, const vvi &par ){
    return depth[ u ] + depth[ v ] - 2 * depth[ getLCA( u, v, depth, par ) ];
}

void bfs( vi &dis, deque< int > que, const vvi &G ){
    while( !que.empty() ){
        int u = que.front();
        que.pop_front();
        for( int nu : G[ u ] )
            if( dis[ nu ] > dis[ u ] + 1 )
                dis[ nu ] = dis[ u ] + 1,
                que.push_back( nu );
    }
}

int main(){
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    cout.tie( 0 );

    int N, M; cin >> N >> M;

    vvi G( N );
    for( int i = 0; i < N - 1; ++i ){
        int a, b; cin >> a >> b;
        --a, --b;
        G[ a ].push_back( b );
        G[ b ].push_back( a );
    }

    vi depth( N );
    vvi par( 20, vi( N ) );
    for( int i = 0; i < 20; ++i )
        fill( par[ i ].begin(), par[ i ].end(), -1 );
    fillTable( 0, -1, 0, G, depth, par );
    for( int i = 0; i + 1 < 20; ++i )
        for( int u = 0; u < N; ++u )
            if( par[ i ][ u ] != -1 )
                par[ i + 1 ][ u ] = par[ i ][ par[ i ][ u ] ];

    vi dis( N, 1e9 ); dis[ 0 ] = 0;
    bfs( dis, { 0 }, G );

    vi lazy_set;
    for( int i = 0; i < M; ++i ){
        int op, v; cin >> op >> v;
        --v;
        if( op == 1 ){
            lazy_set.push_back( v );
            if( lazy_set.size() > BSIZE ){
                deque< int > que;
                for( int u : lazy_set )
                    que.push_back( u ),
                    dis[ u ] = 0;
                lazy_set.clear();
                bfs( dis, que, G );
            }
        } else{
            int ans = dis[ v ];
            for( int u : lazy_set )
                ans = min( ans, getDis( u, v, depth, par ) );
            cout << ans << "\n";
        }
    }

    return 0;
}