倍增法求LCA模板 / p3379

前言

倍增法主要分为三个步骤：

1. 读入图后，进行遍历，获得deep[]深度数组和fa[i][0]父节点数组
2. 进行dp/状态转移获得 f a [ i ] [ 2 j ] fa[i][2^j] fa[i][2j]，即第 2 j 2^j 2j个祖先
3. 对于待查询点u, v，先让它们到达统一深度，再去循环访问它们的第 2 j 2^j 2j个祖先

至此，便完成了整个查询过程，时间复杂度是 O ( n log ⁡ n ) + q O ( log ⁡ n ) O(n \log n)+qO(\log n) O(nlogn)+qO(logn)，q是查询次数

一、例题 p3379

二、思路及代码 1.思路

纯模板题，直接套板子

2.代码

代码如下：

#include 
#include 
using namespace std;
const int maxn = 500005;
struct e {
  int to, next;
} edge[maxn