LCA（菜鸟笔记）
LCA就是求树上两个节点的最近的公共祖先。
我们定义一个节点的祖先是这个节点向根节点走时所经过的所有节点并且包括该节点本身。
LCA（暴力）
介绍一下比较暴力的求两个节点的LCA。
我们现在有两个节点 \(u\) 和 \(v\)，求它们的LCA。我们从 \(u\) 出发一直走到根节点，期间标记走过的所有节点。再从 \(v\) 出发，也标记经过的节点，直到遇到标记的节点已被标记，这个节点即为这两个点的LCA。
LCA（倍增）
介绍一下常见的求LCA的做法。这里我们采用了倍增的思想。
设树上总节点个数为 \(N\)，设 \(depth[i]\) 表示第 \(i\) 个点在树中的深度（根节点的深度为 \(0\)），设 \(fa[i][k]\) 为节点 \(i\) 向上跳 \(2^k\) 步后所到的节点。定义一个哨兵 \(f[i][k]\) 为当节点 \(i\) 向上跳 \(2^k\) 步且跳出根节点的该值为 \(0\)（哨兵是用来防止越界的）。
首先初始化是 \(depth[root] = 1\)，\(f[root][k] = 0 \ ( \ k\in[0,log_2(N)] \ )\)，\(f[0][k] = 0 \ ( \ k\in[0,log_2(N)] \ )\)。
接着我们使用 \(bfs\) 来求 \(depth\)，且对于每一个遍历到的点我们都要求一下它的 \(f\) 函数。这里用倍增的思想来求。节点 \(i\) 要向上跳 \(2^k\) 步可以转变成节点 \(i\) 要向上跳 \(2^{k-1}\) 步后再向上跳 \(2^{k-1}\)。即：
\(k\) 等于 \(0\) 的情况表示的是节点 \(i\) 向上跳 \(1\) 步，那么 \(f[i][0]\) 就等于父节点。
求完了 \(depth\) 和 \(f[i][k]\) 就可以求 \(LCA(a, b)\) 函数了。\(LCA(a, b)\) 函数我们首先判断一下 \(a\) 的深度是否小于 \(b\) 的深度，是的话交换 \(a\) 与 \(b\)。如果深度不同我们需要将 \(a\) 跳到与 \(b\) 深度相同的位置。我们对 \(k\in[0, log_2(N)]\) 从大到小来枚举，当 \(depth[f[a][k]]\ge depth[b]\) 时就令 \(a = f[a][k]\)，即向上跳 \(2^k\) 步，实际上这里是使用了二进制优化，不懂自己查查吧。
接着 \(a\) 与 \(b\) 深度相同后判断 \(a\) 与 \(b\) 是否是同一个点，是的话就找到了它们的 \(LCA\)。
否则 \(a\) 与 \(b\) 需要一起向上跳，跳到 \(a\) 与 \(b\) 的最近公共祖先的儿子节点，然后返回 \(f[a][0]\) 即为它们的 \(LCA\)。为什么不是跳到相同的节点呢？原因是我们向上跳不同的步数其实有可能节点是一样的，这样的话难以判断是不是它们的最近公共祖先，因此我们使用了上述的判断方法，即 \(f[a][k] != f[b][k], \ k\in[0, log_2(N)]\)，且 \(k\) 从大到小遍历。
LCA（求次小生成树）
用LCA求次小生成树。次小生成树分为严格次小生成树和非严格次小生成树。严格次小生成树即树上的边的和大于最小生成树，非严格次小生成树即树上的边的和大于等于最小生成树。
我们知道每条边都有一对点，那么这条边有可能是最小生成树的边，称为树边，也可能不是最小生成树的边，称为非树边。求严格或非严格次小生成树时我们就是遍历每条非树边，对每条非树边我们都暂时将这条边加入树中，那么这两个节点到它们的最近公共祖先的所有边（包括这条非树边）就构成了一个环，那么我们在这个环中减去最大边（不包括非树边），就可能得到严格或非严格最小生成树，对于每条非树边我们都这样做，最终可以得到严格或非严格次小生成树。
用LCA求非严格次小生成树时，我们只要在求 \(f[i][k]\) 时同时求出从节点 \(i\) 跳 \(2^k\) 步后所经过的最大边并记录到数组 \(d1[i][k]\) 中即可。即
当 \(k = 0\) 时，\(d1[i][k]\) 等于从节点 \(i\) 到父节点的那条边的权值，最初 \(k = 0\) 时不要忘记这条边。
用LCA求严格次小生成树我们也是在求 \(f[i][k]\) 时同时求出从节点 \(i\) 跳 \(2^k\) 步后所经过的最大边和从节点 \(i\) 跳 \(2^k\) 步后所经过的次大边，分别记录到 \(d1[i][k]\) 和 \(d2[i][k]\)。起初 \(k = 0\) 时，\(d1[i][k]\) 等于节点 \(i\) 跳到它的父亲的边的权值，而 \(d2[i][k]\) 为负无穷。对于每次跳的 \(2^k\) 步，我们都将 \(d1[i][k-1]\)，\(d2[i][k-1]\)，\(d1[d1[i][k-1]][k-1]\)，\(d2[d2[i][k-1]][k-1]\)取出来然后按照下面的代码来取 \(d1\) 和 \(d2\) 数组的相应值。
int distance[4] = { d1[i][k - 1], d2[i][k - 1], d1[d1[i][k - 1]][k - 1], d2[d2[i][k - 1][k - 1] };
for (int i = 0; i < 4; i++)
{
int d = distance[i];
if (d > d1[j][k])d2[j][k] = d1[j][k], d1[j][k] = d;
else if (d != d1[j][k] && d > d2[j][k])d2[j][k] = d;
}