LCA模板(倍增)

LCA(Lowest Common Ancestor): 树中两个节点深度最大的公共祖先.

思想: 类似ST表，打倍增。预处理出每个节点的深度后，不是一个个跳，而是跳着跳。一次跳2的k次方. 核心: f[i][j]表示i向上跳2^j的父节点。 f[i][j] = f[f[i][j-1]][j-1] 时间复杂度: 预处理O(nlogn)，单次查询O(logn)

fa[i][j]:节点i向上跳2^j的父节点 lg[i]:log(i)+1 dep[i]:深度

写法: 1.dfs预处理深度和fa数组，预处理lg数组,lg[x]表示log(x)+1 2.求LCA(x,y) [1] 不妨假设x的深度 >= y的深度，不是则交换 [2] 让x向上跳，跳到和y同一深度。用到二进制拆位的思想，从最大的能跳的k开始枚举。 [3] x、y一起跳，若fa[x][k] == fa[y][k],是公共祖先，但是不一定是LCA。所以我们为了避免误判，跳到LCA下边一层，避免误判。

例题

模板:

#include
using namespace std;
const int N = 5e5+10;
int n,m,k,T;
int e[N