最近公共祖先LCA(链剖) 给定一棵 以 sss 为根节点,共有 nnn 个点的树。 有 mmm 次查询 每次查询 u,vu ,vu,v 的最近公共祖先。 算法流程 111.根据连边的信息建图(邻接表)。代码就不贴了,注意建立双向边。 222.dfs1dfs1dfs1 ,从给定的起点出发,预处理以下信息: 111深度:deep[e[i].to]=deep[x]+1deep[e[i].to] = deep[x]+1deep[e[i].to]=deep[x]+1 222父亲:fa[e[i].to]=xfa[e[i].to] = xfa[e[i].to]=x 333大小:size[x]+=dfs