祖先跳跃与 LCA

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

int main() {
vector<int>parent{0,0,0,1,1},depth{0,1,1,2,2};int up[5][3];
for(int i=0;i<5;++i)up[i][0]=parent[i];for(int k=1;k<3;++k)for(int i=0;i<5;++i)up[i][k]=up[up[i][k-1]][k-1];
int u=3,v=4;for(int k=2;k>=0;--k)if(up[u][k]!=up[v][k]){u=up[u][k];v=up[v][k];}int ancestor=u==v?u:parent[u];
cout<<ancestor<<" "<<depth[3]+depth[4]-2*depth[ancestor];
}

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

int main() {
vector<int>parent{0,0,0,1,1},depth{0,1,1,2,2};int up[5][3];
for(int i=0;i<5;++i)up[i][0]=parent[i];for(int k=1;k<3;++k)for(int i=0;i<5;++i)up[i][k]=up[up[i][k-1]][k-1];
int u=3,v=4;for(int k=2;k>=0;--k)if(up[u][k]!=up[v][k]){u=up[u][k];v=up[v][k];}int ancestor=u==v?u:parent[u];
cout<<ancestor<<" "<<depth[3]+depth[4]-2*depth[ancestor];
}