LCA（最近公共祖先）专项测试题（含详细答案解析）

LCA（最近公共祖先）专项测试题（含详细答案解析）适用场景：算法入门、CSP/NOIP初赛&复赛基础训练、树论专项刷题考察范围：LCA概念理解、暴力朴素算法、倍增算法、深度性质应用、树上基础建模难度分级：基础60分+中档40分，满分100分做题说明：无特殊说明，树为无根树、无环、连通，节点编号从1开始一、选择题（每题5分，共20分）1.关于树上两个节点u、v的最近公共祖先（LCA），下列说法正确的是？A.LCA一定是u和v中深度更大的节点B.LCA是同时是u、v祖先的所有节点中，深度最大的节点C.任意两个节点的LCA唯一且一定是根节点D.子节点的LCA一定是其父节点2.在一棵有根树中，若节点u是节点v的祖先，则LCA(u,v)等于？A.根节点B.uC.vD.无法确定3.求解LCA的倍增算法，预处理的核心作用是？A.快速计算节点深度B.预处理每个节点的2^k级祖先，实现跳跃式上跳C.统计子树节点数量D.遍历整棵树的所有边4.树上两点u、v的最短路径长度，可通过哪个公式计算（depth为节点深度）？A.depth[u]+depth[v]B.depth[u]-depth[v]+depth[lca]C.depth[u]+depth[v]-2*depth[lca(u,v)]D.depth[u]+depth[v]-depth[lca(u,v)]二、填空题（每空4分，共20分）1.一棵树有n个节点，最多有________条边。2.倍增求解LCA时，一般预处理最大层数log2(n)，对于n≤100000的数据，通常取最大层数为________即可满足需求。3.若两个节点u、v在同一条竖直链上（一个是另一个的祖先），则它们的LCA是________。4.朴素LCA算法（暴力上跳）的单次查询时间复杂度为________，倍增LCA单次查询时间复杂度为________。三、简答题（10分）简述朴素LCA算法的执行流程，并说明其优缺点。四、编程应用题（共50分）题目描述给定一棵包含n个节点的无根树，以1号节点为根。有m次询问，每次询问给出两个节点u、v，输出它们的最近公共祖先。输入格式第一行两个整数n,m，表示节点数和询问数。接下来n-1行，每行两个整数x,y，表示x和y之间有一条无向边。接下来m行，每行两个整数u,v，表示一组询问。输出格式对于每组询问，输出一行一个整数，为u、v的LCA。数据范围1≤n,m≤50000样例输入PlainText

73

12

13

24

25

36

37

45

46

57样例输出PlainText

2

1

1完整答案与详细解析一、选择题答案解析1.答案：B解析：LCA的标准定义为：两节点公共祖先中深度最大、距离两点最近的节点。A错误，LCA深度一定小于等于两节点；C错误，LCA不一定是根节点；D错误，不同父节点的子节点，LCA可能是更上层的祖先。2.答案：B解析：若u是v的祖先，那么u是u、v的公共祖先，且没有更深的公共祖先，因此LCA(u,v)=u。3.答案：B解析：倍增算法核心预处理up[k][u]表示u的2^k级祖先，通过二进制拆分，让节点快速向上跳跃，大幅优化查询速度。4.答案：C解析：u到根、v到根的路径总和，减去两倍的LCA到根的路径（重复部分），即为u、v最短路径长度，是树上路径长度通用公式。二、填空题答案解析1.n-1解析：树的定义为n个节点的连通无环图，固定有n-1条边。2.20解析：2^20≈1e6，大于1e5，可覆盖100000以内的所有节点跳跃需求。3.深度较小的那个节点（祖先节点）4.O(n)、O(logn)解析：朴素算法最坏需要遍历整条树链，单次O(n)；倍增预处理O(nlogn)，单次查询仅需logn次跳跃，复杂度O(logn)。三、简答题答案算法流程：1.先通过DFS/BFS预处理整棵树，记录每个节点的父节点和深度；2.对于查询的两个节点u、v，先将深度更大的节点向上跳跃，直到两节点深度相等；3.若此时两节点相等，直接返回该节点为LCA；4.若不相等，两节点同时一步步向上跳父节点，直到两节点的父节点相同，该父节点即为LCA。优缺点：优点：思路简单、代码易懂、无需复杂预处理，适合小规模数据；缺点：查询效率极低，大数据量（n、m上万）会超时，无法应对竞赛高频查询场景。四、编程题详细题解+完整AC代码（C++）解题思路采用倍增LCA算法，适配5e4数据范围，不超时、效率稳定。1.建图：用邻接表存储无向树；2.DFS预处理：每个节点的深度、2^0级祖先（直接父节点）；3.倍增预处理：递推求出每个节点的2^1、2^2...2^20级祖先；4.查询函数：先对齐两点深度，再同步上跳，找到最近公共祖先。完整AC代码PlainText

#include<iostream>

#include<vector>

#include<cstring>

usingnamespacestd;

constintN=50010;

constintLOG=20;

vector<int>g[N];

intup[LOG][N];

intdepth[N];

//dfs预处理深度和父节点

voiddfs(intu,intfa)

{

up[0][u]=fa;

depth[u]=depth[fa]+1;

for(intv:g[u])

{

if(v!=fa)

{

dfs(v,u);

}

}

}

//倍增预处理

voidinit(intn)

{

memset(up,0,sizeof(up));

depth[0]=0;

dfs(1,0);//根为1，根的父节点为0

for(intk=1;k<LOG;k++)

{

for(inti=1;i<=n;i++)

{

up[k][i]=up[k-1][up[k-1][i]];

}

}

}

//LCA查询函数

intlca(intu,intv)

{

if(depth[u]<depth[v])swap(u,v);

//把u跳到和v同一深度

intdiff=depth[u]-depth[v];

for(intk=0;k<LOG;k++)

{

if(diff&(1<<k))

{

u=up[k][u];

}

}

if(u==v)returnu;

//同步上跳

for(intk=LOG-1;k>=0;k--)

{

if(up[k][u]!=up[k][v])

{

u=up[k][u];

v=up[k][v];

}

}

returnup[0][u];

}

intmain()

{

ios::sync_with_stdio(false);

cin.tie(0);

intn,m;

cin>>n>>m;

for(inti=1;i<n;i++)

{

intx,y;

cin>>x>>y;

g[x].push_back(y);

g[y].push_back(x);

}

init(n);

while(m--)

{

intu,v;