倍增LCA：从入门到入土
题单介绍
模版代码（vector）：
```cpp
const int N,lg;
int deep[N],f[N][lg+1],n/*n:点数，边数为n-1*/;
vector<int>v[N];
void add(int x,int y){
v[x].push_back(y);
v[y].push_back(x);
}
void build(int x){
for(int i=0;i<v[x].size();i++){
int p=v[x][i];
if(!deep[p]){
deep[p]=deep[x]+1;
f[p][0]=x;
build(p);
}
}
}
void dp(){
for(int j=1;j<=lg;++j)
for(int i=1;i<=n;++i)
f[i][j]=f[f[i][j-1]][j-1];
}
int lca(int x,int y){
if(deep[x]<deep[y])swap(x,y);
for(int i=lg;i>=0;i--)if(deep[f[x][i]]>=deep[y])x=f[x][i];
if(x==y)return x;
for(int i=lg;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][0];
}
```
较简单的倍增 LCA 集合（按个人做题难度升序排列）。
P3379：模版，一切的基础。
P10113：加入附加最大值条件，本质一致，改动不大。
P8855：初步求路径长度。
P8805：前缀和思想应用，点权前缀和。
P4281：路径进阶，但仔细想想能想出来。
P5836：加入状态判断。
*P8972*：重点是**树上边权前缀和**的使用。
P3128：纯模板树上差分。
*P3258*：初步加入差分。
P3398：路径的思维进阶。
P6374：小清新找规律题。
P1967：初步加入生成树。
P2680：二分+树上差分。
*P4180*：生成树进阶。
P4271：加入树的直径，需要维护 LCA 和树的直径。
可以自行安排顺序，也可借鉴我给出的顺序。全部 AC 后，简单的倍增 LCA 题应当可以轻松 A 掉。