# 洛谷 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分

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455 #include #include #include #include using namespace std; int n, m, s; vector edges[500005],askPair[500005]; bool visited[500005]; int father[500005]; inline int _find(int node) {     if (father[node]==-1)return node;     return father[node] = _find(father[node]); } inline void _union(int x, int y) {     if(_find(x)!=_find(y))father[_find(x)] = y; } struct ask {     int u, v;     int ans; }asks[500005]; inline int checkV(int id,int node) {     if (asks[id].u != node)return asks[id].u;     return asks[id].v; } void dfs(int node,int fath) {     for (int i = 0; i < edges[node].size(); i++) {         if (edges[node][i] == fath)continue;         dfs(edges[node][i],node);         _union(edges[node][i], node);     }     visited[node] = true;     for (int i = 0; i < askPair[node].size(); i++) {         int v = checkV(askPair[node][i], node);         if (visited[v])asks[askPair[node][i]].ans = _find(v);     } } int main() {     memset(father, -1, sizeof(father));     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);     }     for (int i = 1; i <= m; i++) {         cin >> asks[i].u >> asks[i].v;         askPair[asks[i].u].push_back(i);         askPair[asks[i].v].push_back(i);     }     dfs(s,s);     for (int i = 1; i <= m; i++)cout << asks[i].ans << "\n"; }

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

Tarjan::

 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465 #include using namespace std; int edge_ptr = 0; struct edge{     int v;     int next; }edges[1000005]; int head[500005]; int n, m, s; int father[500005][25],depth[500005]; bool visited[500005]; inline void insert_edge(int s,int t){     edge_ptr++;     edges[edge_ptr].v = t;     edges[edge_ptr].next = head[s];     head[s] = edge_ptr; } inline void dfs(int u){     visited[u] = true;     for (int i = 1, len = 1; len <= depth[u]; i++, len <<= 1){         father[u][i] = father[father[u][i - 1]][i - 1];     }     for (int e = head[u]; e != -1;e=edges[e].next){         if (!visited[edges[e].v]){             depth[edges[e].v] = depth[u] + 1;             father[edges[e].v][0] = u;             dfs(edges[e].v);         }     } } inline int query(int x, int y){     if (depth[x] > depth[y])swap(x,y);     int diff = depth[y] - depth[x];     for (int i = 0, two = 1; diff != 0; two <<= 1, i++){         if (diff&two){             y = father[y][i];             diff -= two;         }     }     if (x == y)return x;     for (int i = log2(depth[x]); i >= 0; i--){         if (father[x][i] != father[y][i]){             x = father[x][i];             y = father[y][i];         }     }     return father[x][0]; } int main(){     ios::sync_with_stdio(false);     memset(head, -1, sizeof(head));     cin >> n >> m >> s;     for (int i = 1; i <= n - 1; i++){         int x, y;         cin >> x >> y;         insert_edge(x, y);         insert_edge(y, x);     }     dfs(s);     for (int i = 1; i <= m; i++){         int x, y;         cin >> x >> y;         cout << query(x, y) << endl;     } }