整理日期按学习顺序编排，不代表原始发表时间。实际整理于 2026-10-23。

难度为阅读建议，可从 ACM 学习索引 按阶段阅读。

倍增求lca

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct edge{
    int v,w;
};
//思考：要想知道一个数有几个二级制位，直接n=__lg(x)
//我们可以知道<n最近的2的次幂，9最大的是8，8虽然是2的3次方，但要遍历它的每一位
//需要3到0开始，也就是考虑到0的影响，我们可以正好满足偏移。
//2的3次方有四位，也就是__lg(x)就是我们需要的最高位，从它开始往低遍历
vector<edge>e[N];
int dep[N];
int d[N];
const int len=__lg(N);
int f[N][len+2];
int cnt[N];
int ans=0;
void dfs(int u,int fa){
    dep[u]=dep[fa]+1;
    f[u][0]=fa;
    for(int i=1;i<=len;i++)f[u][i]=f[f[u][i-1]][i-1];
    //预处理倍增数组

    for(auto [v,w]:e[u]){
        if(v==fa)continue;
        d[v]=d[u]+w;
        dfs(v,u);
    }
}

int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=len;i>=0;i--){
        if(dep[f[x][i]]>=dep[y])x=f[x][i];
    }
    //跳到相同深度

    if(x==y)return y;
    //提提前判本身就是祖先关系


    for(int i=len;i>=0;i--){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];y=f[y][i];
        }
    }
    //倍增一起向上跳，直到父亲就是答案
    return f[x][0];
}