K - 巨大企業 / Conglomerate ~LCA~

Code

// LCA set
VV G;
const int N_MAX = 150010;
const int MAX_LOG_V = 20;
ll depth[N_MAX] = {};
ll parent[MAX_LOG_V][N_MAX] = {};
void dfs(ll index, ll prev, ll _depth){
    depth[index] = _depth;
    parent[0][index] = prev;
 
    for(ll to : G[index]){
        if(to==prev){
            continue;
        }
        dfs(to, index, _depth+1);
    }
    return;
}
ll LCA(ll a, ll b){
    if(a==b){
        return a;
    }
    // aよりbが深い(または同じ)と仮定する
    if(depth[a] > depth[b]){
        swap(a, b);
    }
    // bを根側に辿っていく
    ll diff_depth = depth[b] - depth[a];
    FOR(k, 0, MAX_LOG_V){
        if(diff_depth >> k & 1){
            b = parent[k][b];
        }
    }
    // aとbの深さが揃った
    if(a==b){
        return a;
    }
    // 大きい歩幅で共通親までジャンプ
    for(int k=MAX_LOG_V-1; k>=0; k--){
        if(parent[k][a] != parent[k][b]){
            a = parent[k][a];
            b = parent[k][b];
        }
    }
    // 1つ上がLCA
    return parent[0][a];
}
ll dist(ll a, ll b){
  if(a==b)return 0;
  ll l = LCA(a,b);
  return depth[a]+depth[b]-2*depth[l];
}
void prepare_LCA(ll N, ll root=0){
    dfs(root, -1, 0);
    // ダブリングで親 2^k
    FOR(k, 1, MAX_LOG_V){
      // FOR(i, 1, N+1){
      FOR(i, 0, N){
        ll p = parent[k-1][i];
        if(p==-1) continue;
        parent[k][i] = parent[k-1][p];
      }
    }
}
// LCA set end

その他

グラフ描画

20 19
1 4
2 11
3 12
5 1
6 13
7 13
8 4
9 6
10 20
11 1
12 1
13 20
14 10
15 8
16 8
17 20
18 10
19 18
20 1

f:id:peroon:20200102020127p:plain

verified (LCA)