# 洛谷 P3379 【模板】最近公共祖先（LCA）重写

 1234567891011121314151617181920212223242526272829303132333435363738 #include #include using namespace std; int n, m, s; vector edges[500005]; int father[500005],depth[500005]; void dfs(int node, int fath) {     father[node] = fath;     depth[node] = depth[fath] + 1;     for (int i = 0; i < edges[node].size(); i++) {         if (edges[node][i] == fath)continue;         dfs(edges[node][i], node);     } } int query(int a, int b) {     while (a != b) {         if (depth[a] >= depth[b])a = father[a];         else b = father[b];     }     return a; } int main() {     ios::sync_with_stdio(false);     cin.tie(0);     cin >> n >> m >> s;     for (int i = 1; i <= n - 1; i++) {         int x, y;         cin >> x >> y;         edges[x].push_back(y);         edges[y].push_back(x);     }     dfs(s, s);     for (int i = 1; i <= m; i++) {         int a, b;         cin >> a >> b;         cout << query(a, b) << "\n";     } }

 123456789101112131415161718192021222324252627282930313233343536373839404142434445 #include #include #include #define MAXLOG 20 using namespace std; int n, m, s; vector edges[500005]; int depth[500005]; int ancestor[500005][MAXLOG+2]; void dfs(int node, int fath) {     ancestor[node][0] = fath;     depth[node] = depth[fath] + 1;     for (int i = 1; i <= MAXLOG; i++)ancestor[node][i] = ancestor[ancestor[node][i - 1]][i - 1];     for (int i = 0; i < edges[node].size(); i++) {         if (edges[node][i] == fath)continue;         dfs(edges[node][i], node);     } } int query(int a, int b) {     if (depth[b] > depth[a])swap(a, b);     for (int i = MAXLOG; ~i; i--)if (depth[ancestor[a][i]] >= depth[b])a = ancestor[a][i];     if (a == b)return a;     for (int i = MAXLOG; ~i; i--) if(ancestor[a][i]!=ancestor[b][i]){         a = ancestor[a][i];         b = ancestor[b][i];     }     return ancestor[a][0]; } int main() {     ios::sync_with_stdio(false);     cin.tie(0);     cin >> n >> m >> s;     for (int i = 1; i <= n - 1; i++) {         int x, y;         cin >> x >> y;         edges[x].push_back(y);         edges[y].push_back(x);     }     dfs(s, s);     for (int i = 1; i <= m; i++) {         int a, b;         cin >> a >> b;         cout << query(a, b) << "\n";     } }

Tarjan:洛谷70分，O2 100分