题目描述
如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N-1N−1 行每行包含两个正整数 x, yx,y，表示 xx 结点和 yy 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 MM 行每行包含两个正整数 a, ba,b，表示询问 aa 结点和 bb 结点的 最近公共祖先。
输出格式
输出包含 MM 行，每行包含一个正整数，依次为每一个询问的结果。
输入输出
样例 1
输入
5 5 4 3 1 2 4 5 1 1 4 2 4 3 2 3 5 1 2 4 5
输出
4 4 1 4 4
说明/提示
对于 30% 的数据，N≤10，M≤10。
对于 70% 的数据，N≤10000，M≤10000。
对于 100% 的数据，N≤500000，M≤500000。
PICTURE:/home/ldu/.config/tencent-qq//AppData/file//sendpix2.jpg
在进行倍增的时候，考虑跳的步长从大到小进行安排，并且求一下log来优化
一些小细节：
对于该题可以采取链式前向星建图（vector也无所谓），再加边的时候应该注意是双向边，而不是单向的边
代码详解：
一：初始化头结点为-1
void init(){ for(int i=1;i<=n;i++) head[i] = -1; }
二：对输入数据进行加边操作：
void add(int u,int v){ e[cnt].u = u; e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt ++; }
三：对于里面的DFS操作，就是对某一个节点的2^j级祖先进行预处理，采用DFS的方式来进行递归，表示在数组里面就是fa[x][j] ,在求解的过程中还要递归处理节点的深度，对给出的树根，可以巧妙的处理为这颗树根的祖先节点是0这个点，然后他的深度是1，在递归的过程中cur表示当前节点，而rt表示这个节点的根节点（也就是祖先节点），然后就可以在递归的过程中，将这个点的深度depth[cur] = depth[fa] + 1。
然后下面的for循环处理fa数组，这个循环所能走的最大2^j级祖先最大的j可以对他预处理一个log，也就是下面的 cal 函数。处理完之后就可以遍历和这个节点相连的所有节点，当这个点不是这个节点的根节点也就是rt的时候，对他进行递归的DFS处理，此时在传递参数的时候父亲节点就是cur，当前节点就是与其相连的节点
void dfs(int cur,int rt){ fa[cur][0] = rt,dep[cur] = dep[rt] + 1;/// the depth of the current node changed for(int i=1;i <= lg[dep[cur]];i++){ fa[cur][i] = fa[fa[cur][i-1]][i-1]; } for(int i=head[cur];~i;i = e[i].next){/// visit all linked nodes if(e[i].v != rt) dfs(e[i].v,cur); } }
四：lca函数
我们在处理的过程中，默认x节点的深度比y深，所以说如果说x深度比y深度小，就直接交换两个节点，方便下次进行处理
然后一直遍历，当x深度一直大于y深度的时候，我们对x一直进行转移
然后我们在下面从大到小转移节点，同时对两个节点进行转移处理，从大到小的过程中我们对他处理的过程是：根据预先处理的log大小到0，来进行从大到小的跳转，在跳转的过程中，我们要避免讲两个点跳转到同一个节点，如果能跳转到的节点不相同我们就跳转，相同的情况下不进行跳转；
关于为什么从大到小：从大到小的过程中一定有一种方式能够将这个数唯一的表示出来，而且不存在所谓的“反悔”的情况
在最后返回的时候，返回fa[x][0]即为答案
int lca(int x,int y){ if(dep[x] < dep[y]) swap(x,y); while(dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1]; if(x == y) return y; /// big -> small for(int k = lg[dep[x]] - 1;k >= 0;k --){ if(fa[x][k] != fa[y][k]){ x = fa[x][k]; y = fa[y][k]; } } return fa[x][0]; }
有待完善
欢迎批评指正
版本一时间：2021-03-07-22:11
int n,m; int root; int head[maxn]; struct node{ int u; int v; int next; }e[maxn]; int dep[maxn];/// save the depth of every node int fa[maxn][30]; int lg[maxn]; int cnt = 0; void init(){ for(int i=1;i<=n;i++) head[i] = -1; } void add(int u,int v){ e[cnt].u = u; e[cnt].v = v; e[cnt].next = head[u]; head[u] = cnt ++; } void dfs(int cur,int rt){ fa[cur][0] = rt,dep[cur] = dep[rt] + 1;/// the depth of the current node changed for(int i=1;i <= lg[dep[cur]];i++){ fa[cur][i] = fa[fa[cur][i-1]][i-1]; } for(int i=head[cur];~i;i = e[i].next){/// visit all linked nodes if(e[i].v != rt) dfs(e[i].v,cur); } } void cal(){ for(int i=1;i<=n;i++){ lg[i] = lg[i-1] + (1 << lg[i-1] == i);/// 2 ^ lg[i-1] == i true + 1 } } int lca(int x,int y){ if(dep[x] < dep[y]) swap(x,y); while(dep[x] > dep[y]) x = fa[x][lg[dep[x] - dep[y]] - 1]; if(x == y) return y; /// big -> small for(int k = lg[dep[x]] - 1;k >= 0;k --){ if(fa[x][k] != fa[y][k]){ x = fa[x][k]; y = fa[y][k]; } } return fa[x][0]; } int main() { ///freopen("1.in","r",stdin); ///freopen("1.out","w",stdout); cin >> n >> m >> root; cal(); init(); for(int i=1;i<n;i++){ int x = read,y = read; add(x,y); add(y,x); } dfs(root,0); for(int i=1;i<=m;i++){ int x = read,y = read; printf("%d\n",lca(x,y)); } return 0; }/// ac_code
