CFR 519 E. A and B and Lecture Rooms ( LCA )

Problem - 519E - Codeforces
首先如果 a, b的路徑長為奇數，那麼解為 0。如果 a = b，那麼解為 N。
所以關注路徑長為偶數的情況，顯然要先找到路徑的中點，令它為 c。
為求方便，使 a的深度大於 b。
若 c為 a和 b的祖先，那麼答案是 N - ( c 連接有 a節點的子樹大小 ) - ( c 連接有 b節點的子樹大小 )
否則 c介於 a和 b之間，答案是 size[ c ] - ( c 連接有 a節點的子樹大小 )

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

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

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

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

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

    if( a == b ) return a;

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

    return par[ 0 ][ a ];
}

int getAnc( int u, int n, const vvi &par ){
    for( int i = 19; n; --i )
        if( n >= 1 << i )
            u = par[ i ][ u ],
            n -= 1 << i;
    return u;
}

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

    int N; cin >> N;

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

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

    dfs( 0, -1, 0, G, depth, size, par );

    for( int i = 0; i + 1 < 20; ++i )
        for( int j = 0; j < N; ++j ){
            if( par[ i ][ j ] == -1 ) continue;
            int k = par[ i ][ j ];
            par[ i + 1 ][ j ] = par[ i ][ k ];
        }

    int M; cin >> M;
    for( int i = 0; i < M; ++i ){
        int a, b; cin >> a >> b;
        --a, --b;
        if( a == b ){
            cout << N << "\n";
            continue;
        }
        if( not ( depth[ a ] > depth[ b ] ) )
            swap( a, b );

        int c = getLCA( a, b, depth, par );

        int dis = depth[ a ] + depth[ b ] - 2 * depth[ c ];
        if( dis & 1 ){
            cout << 0 << "\n";
            continue;
        }

        int mid = getAnc( a, dis / 2, par );
        if( mid == c ){
            int u = getAnc( a, dis / 2 - 1, par );
            int v = getAnc( b, dis / 2 - 1, par );
            cout << N - size[ u ] - size[ v ] << "\n";
        }
        else{
            int u = getAnc( a, dis / 2 - 1, par );
            cout << size[ mid ] - size[ u ] << "\n";
        }
    }

    return 0;
}