LCA及例题

倍增法求LCA

简单说就是先通过dfs预处理出每个节点i的深度deep[i]与其的第\(2^j\)个祖先f[i][j]。求f[i][j]的关键在于递推式f[i][j]=f[f[i][j-1]][j-1]。也即i的 \(2^j\) 祖先是 \(2^{j-1}\) 祖先的 \(2^{j-1}\) 祖先。
再求\(LCA\):首先将两节点的高度提升到同一水平，再同时提升两节点直至其父节点相同。当然，为了保证效率，两次提升都应该通过倍增法进行。
最终空间复杂度O(nlogn)，预处理时间O(nlogn)，单次查询时间O(logn)

const int N;//最多有N个节点
int n,deep[N],f[N][log_N];
vector<int> G[N];//无根树保存在这里

void dfs(int u,int ufa){ //预处理，ufa是u的父节点
    deep[u]=deep[ufa]+1;
    f[u][0]=ufa;
    for(int i=1;(1<<i)<=deep[u];i++)
        f[u][i]=f[f[u][i-1]][i-1];//求u的2^i祖先
    for(unsigned i=0;i<G[u].size();i++)
        if(G[u][i]!=ufa)
            dfs(G[u][i],u);//遍历u的所有儿子进行递归
int LCA(int u,int v){
    if(deep[u]<deep[v]) swap(u,v);//保证deep[u]>=deep[v]
    for(int i=log_n;i>=0;i--)//将u提到和v同一深度
        if(deep[u]>=deep[v]) u=f[u][i];
    if(u==v) return u;
    for(int i=log_n;i>=0;i--)//将u和v同时提升至其父节点相同
        if(f[u][i]!=f[v][i]){
            u=f[u][i];
            v=f[v][i];
        }
    return f[u][0];//此时u,v的父节点就是u,v的LCA
}

LCA的应用

P3379 LCA模板
P3884 二叉树问题
题意：给一棵二叉树，求深度、宽度(节点最多层的节点数)和两点u,v的距离(定义为u到LCA的路径长乘2加上v到LCA的路径长)。

P4281 紧急集合
题意：给出一棵树以及三个点(多组数据)，求与三个点的距离之和最小的点及距离之和。

P3398 仓鼠找sugar
题意：给出一颗树，以及四个数a,b,c,d(多组数据)。询问ab间最短路径与cd间最短路径是否相交。