lca与树上（路径交、并，直径）问题

最近的一些比赛中经常用到树上$lca$的常见模型，整理一下：

首先整理一下$LCA$的四种求法：

1.倍增$LCA$：预处理$O(nlogn)$ 单次查询$O(logn)$

通过$bfs$预处理节点深度和$st$表倍增处理祖宗节点，在查询的时候用倍增先将两点跳到统一深度，再找同祖宗节点的最深节点

int n,depth[N],f[N][19];
vector<int>e[N];
void bfs(int root){
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;//0为st表的哨兵
    queue<int>q;
    q.push(root);
    while(q.size()){
        int ver=q.front();
        q.pop();
        for(auto &to:e[ver]){
            if(depth[to]>depth[ver]+1){
                depth[to]=depth[ver]+1;
                f[to][0]=ver;
                for(int i=1;i<=18;i++)
                f[to][i]=f[f[to][i-1]][i-1];
            }
        }
    }
}
int lca(int a,int b){
    if(depth[a]<depth[b])swap(a,b);
    for(int i=18;i>=0;i--){
        if(depth[f[a][i]]<=depth[b])
        a=f[a][i];
    }
    if(a==b)return a;
    for(int i=18;i>=0;i--){
        if(f[a][i]!=f[b][i])
        a=f[a][i],b=f[b][i];
    }
    return f[a][0];
}

2.$Tarjan$离线$LCA$: 总体时间复杂度$O(n+q)$ ，$n$为节点 $q$为查询次数

暂定

3.在线$RMQLCA$：预处理$O(nlogn)$ 单次查询$O(1)$

通过$dfs$处理欧拉序及其深度，并保存每个节点第一次出现位置，通过$st$表维护区间深度最小值即可

int n,q,root,depth[N<<1],f[N<<1][19],se[N<<1],tot,Log[N<<1],id[N];
vector<int>e[N];
void dfs(int u,int d,int fa){
    se[++tot]=u;
    id[u]=tot;
    depth[tot]=d;
    for(auto &to:e[u]){
        if(to==fa)continue;
        dfs(to,d+1,u);
        se[++tot]=u;
        depth[tot]=d;
    }
}
int lca(int l,int r){
    int k=Log[r-l+1];
    return depth[f[l][k]]<depth[f[r-(1<<k)+1][k]]?
    se[f[l][k]]:se[f[r-(1<<k)+1][k]];
}
void solve(){
    cin>>n>>q>>root;
    for(int i=1;i<n;i++){
        int u,v;cin>>u>>v;
        e[u].pb(v);
        e[v].pb(u);
    }
    dfs(root,1,0);
    Log[1]=0,Log[2]=1;
    for(int i=3;i<=tot;i++)
    Log[i]=Log[i/2]+1;

    for(int i=1;i<=tot;i++)f[i][0]=i;

    for(int j=1;j<=Log[tot];j++)
    for(int i=1;i+(1<<j)-1<=tot;i++)
    if(depth[f[i][j-1]]<depth[f[i+(1<<(j-1))][j-1]])f[i][j]=f[i][j-1];
    else f[i][j]=f[i+(1<<(j-1))][j-1];

    while(q--){
        int u,v;cin>>u>>v;
        int l=id[u],r=id[v];
        if(l>r)swap(l,r);
    }
}

4.树链剖分$LCA$:预处理$O(n)$ 单次查询$O(logn)$

暂定

树上$LCA$的几种常用模型：

1.动态维护树的直径

2.树上路径的交

3.树上路径的并