LCA(Lowest Common Ancesto) 就是今天的主角,又叫最近公共祖先,用来求两个节点的最小父节点。 1.简介 LCA算法是一种倍增算法,分为3个步骤:遍历深度与父节点、倍增初始化和LCA主函数。 2.代码 1.遍历深度与父节点(附main函数调用方式) int n, m, s, f[100005][33],dep[100005];//倍增数组和深度数组 vector<int> a[500005];//结点vector void dfs(int u, int fa){ f[u][0] = fa; dep[u] = dep[fa]+1; for (int i = 0;...