如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
第一行包含三个正整数N、M、S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来N-1行每行包含两个正整数x、y，表示x结点和y结点之间有一条直接连接的边（数据保证可以构成树）。
接下来M行每行包含两个正整数a、b，表示询问a结点和b结点的最近公共祖先。
输出包含M行，每行包含一个正整数，依次为每一个询问的结果。
RT。 原本，看到这种题，想到的应该是从树的下面逐个上跳去寻找。 LCA就是从下往上倍增跳跃。可以省掉许多空余的步骤。 直接跳(可以跳的最大k次方)会节省时间。比如找【5=（二的次方的和）？】，【1+2+？】倒回再【1+4】就比直接【4+1】慢了。（啊啊啊来自luogu某题解） 详见代码算了。
#include<cstdio> #include<algorithm> using namespace std; int n,m,s,t; int l[500001],jump[500001],Deep[500001],father[500001][101]; struct asdf{ int to,next; } A[1000001]; void read(){ //读入 int x,y; scanf("%d%d%d", &n, &m, &s); for(int i = 1; i < n; ++i){ scanf("%d%d", &x, &y); A[++t] = (asdf){y,l[x]}; l[x] = t; //邻接表存储 A[++t] = (asdf){x,l[y]}; l[y] = t; } int k = 1; jump[1] = 1; //预处理jump。jump[i]为在深度为i的时候可以跳2^（i-1）的步数 for(int i = 2; i <= n; ++i){ jump[i] = jump[i-1]; if(i / k == 2){ k*=2; ++jump[i]; } } } void dfs(int now,int fu){ //当前点和父亲//dfs求某节点跳2^k步是哪个节点 father[now][0] = fu; //跳2^0步 Deep[now] = Deep[fu] + 1; //深度统计 for(int i = 1; i <= jump[Deep[now]]; ++i) father[now][i] = father[father[now][i-1]][i-1]; //从当前点跳2^i步=跳了2^(i-1)步的点后再跳2^(i-1)步 for(int i = l[now]; i; i = A[i].next) if(Deep[A[i].to] == 0) dfs(A[i].to,now); } int kmp(int x,int y){ if(Deep[x]>Deep[y]){ //让y的深度大于x的深度 int l = x; x = y; y = l; } while(Deep[x] != Deep[y]) y = father[y][jump[Deep[y] - Deep[x]] - 1]; //让x和y跳到同一高度 //y跳的时候就有倍增跳跃 if(x == y) return x; for(int i = jump[Deep[x]]-1; i>=0; --i) //跳跃 if(father[x][i] != father[y][i]){ //如果父亲不一样就跳过去 //如果父亲一样可能会跳过头 //所以我们的目标是最近公共祖先的子节点 x = father[x][i]; y = father[y][i]; } return father[x][0]; //返回 } int main(){ read(); dfs(s,0); for(int i = 1; i <= m; ++i){ int x,y; scanf("%d%d",&x,&y); printf("%d\n",kmp(x,y)); //输出 } }