Code
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;
}
if(depth[a] > depth[b]){
swap(a, b);
}
ll diff_depth = depth[b] - depth[a];
FOR(k, 0, MAX_LOG_V){
if(diff_depth >> k & 1){
b = parent[k][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];
}
}
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);
FOR(k, 1, MAX_LOG_V){
FOR(i, 0, N){
ll p = parent[k-1][i];
if(p==-1) continue;
parent[k][i] = parent[k-1][p];
}
}
}
その他
グラフ描画
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
verified (LCA)
- No.1094 木登り / Climbing tree - yukicoder
- AOJ
- 035-Preserve Connectivity(★7)