网站怎么注销主体,手机网站建设优势,网站运营推广方案设计,怎么可以做网站概念 最近公共祖先指两个节点在一棵树上深度最大的公共的祖先节点，即这两个点在这棵树上距离最近的公共祖先节点。 Tarjan 算法介绍 使用倍增思想和动态规划。 基本思路：任选一个点为根节点，从根节点开始。 遍历该点… 概念 最近公共祖先指两个节点在一棵树上深度最大的公共的祖先节点，即这两个点在这棵树上距离最近的公共祖先节点。 Tarjan 算法介绍 使用倍增思想和动态规划。 基本思路：任选一个点为根节点，从根节点开始。 遍历该点 u 所有子节点 v ，并标记这些子节点 v 已被访问过。 若是 v 还有子节点，返回 2 ，否则下一步。 合并 v 到 u 上。 寻找与当前点 u 有询问关系的点 v 。 若是 v 已经被访问过了，则可以确认 u 和 v 的最近公共祖先为 v 被合并到的父亲节点 a 。代码 #includebits/stdc++.h using namespace std; const int N = 5e5+10; int idx, e[2*N], nxt[2*N], h[N]; int n, m, s, f[N][30], deep[N]; void add(int u, int v){nxt[++idx] = h[u];h[u] = idx;e[idx] = v; } void dfs(int u, int fa){f[u][0] = fa;for(int i = 1; i = 23; i++) f[u][i] = f[f[u][i-1]][i-1];for(int i = h[u]; i; i = nxt[i]){int v = e[i];if(v == fa) continue;deep[v] = deep[u] + 1;dfs(v, u);} } int lca(int x, int y){if(deep[x] deep[y]) swap(x, y);for(int i = 23; i = 0; i--){if(deep[f[x][i]] = deep[y]) x = f[x][i];}if(x == y) return x;for(int i = 23; i = 0; i--){if(f[x][i] != f[y][i]){x = f[x][i];y = f[y][i];}}return f[x][0]; } int main(){deep[1] = 1;scanf("%d%d%d", n, m, s);for(int i = 1; i n; i++){int u, v;scanf("%d%d", u, v);add(u, v);add(v, u);}dfs(s, s);while(m--){int x, y;scanf("%d%d", x, y);printf("%d\n", lca(x, y));}return 0; }