【图论-树上问题】最近公共祖先（LCA）

CNS_5t0_0r2 · 2024-07-09 08:48:09 · 算法·理论

LCA 的定义/查询相关的已经咕了（请先保证你会倍增求 LCA & 树剖求 LCA），直接讲 LCA 的应用。

【1】求树上任意两点距离

这是 LCA 一个比较简单的应用，对于一个路径 (u,v)，u 到 LCA 的距离为 dep_u - dep_{\operatorname{LCA}}，v 到 LCA 的距离为 dep_v - dep_{\operatorname{LCA}}，所以 u 到 v 的距离为 dep_u + dep_v - 2 dep_{\operatorname{LCA}}，并且不用考虑 u,v 之间互为祖先-子孙关系。

【2】树上差分

树上差分是 LCA 的主要应用。用于维护树上的带修问题。

【2.1】点差分

树上差分和序列差分是类似的，不过在讲树上差分是之前，我们先得搞清楚树上的“前缀和”是什么，以及树上的“区间修改”是什么。

树上的前缀和就是对一个子树求和，在这里我们讨论的区间修改是指链上的修改，这两个看似对不上，但接下来就知道为什么是这样了。

对于一个链 (u,v) 上的修改，可以这样差分：

在 u,v 上打 + k 标记，表示 u,v 的所有祖先都加了 k；同时在 \operatorname{LCA}(u,v) 和 fa_{\operatorname{LCA}(u,v)} 上打 -k 标记，表示 \operatorname{LCA}(u,v) 和fa_{\operatorname{LCA}(u,v)} 的所有祖先都加了 k。这样就会发现路径 u,v 上的所有节点（包括 LCA 在内，因为 LCA 之前被加了 2 次）都刚好被加了一次，其余节点都没被加（或被抵消）。

例题 1：Max Flow P

简化题意：给出一棵 N 个节点的树和 K 次修改，每次修改对路径 [s,t] 上的所有点权加 1，求 K 次修改后权值最大的点。

这不就是树上差分的板子吗？

以下代码使用了常数小的树剖求 LCA：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 9;
struct edge{
    int to,nex;
} e[N << 1];
int ecnt,head[N];
int top[N],dep[N];
int fa[N],w_ch[N],siz[N];//每个节点的父节点、重儿子、子树大小 
void addedge(int u,int v){
    ecnt++;
    e[ecnt] = (edge){v,head[u]};
    head[u] = ecnt;
}
int val[N];
int n,k,ans;
void dfs1(int cur,int father){
    fa[cur] = father;
    siz[cur] = 1;
    dep[cur] = dep[father] + 1;
    for(int i = head[cur];i;i = e[i].nex){
        int v = e[i].to;
        if(v != father){
            dfs1(v,cur);
            siz[cur] += siz[v];
            if(siz[v] > siz[w_ch[cur]])
                w_ch[cur] = v;
        }
    }
}
void dfs2(int cur,int link_top){
    top[cur] = link_top;
    if(w_ch[cur]){//有重儿子（不是叶节点） 
        dfs2(w_ch[cur],link_top);
        for(int i = head[cur];i;i = e[i].nex){
            int v = e[i].to;
            if(v != fa[cur] && v != w_ch[cur])
                dfs2(v,v);
        }
    }
}
int LCA(int u,int v){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]])
            swap(u,v);
        u = fa[top[u]];
    }
    return (dep[u] < dep[v]) ? u : v;
}

void dfs3(int cur){
    for(int i = head[cur];i;i = e[i].nex){
        int v = e[i].to;
        if(v != fa[cur]){
            dfs3(v);
            val[cur] += val[v];
        }
    }
    ans = max(ans,val[cur]);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for(int i = 1;i < n;i++){
        int u,v;
        cin >> u >> v;
        addedge(u,v);
        addedge(v,u);
    }
    dep[1] = 1;
    dfs1(1,-1);
    dfs2(1,-1);
    for(int i = 1;i <= k;i++){
        int u,v;
        cin >> u >> v;
        val[u]++;val[v]++;
        int lca = LCA(u,v);
        val[lca]--;val[fa[lca]]--;
    }
    dfs3(1);
    cout << ans;
    return 0;
}

例题 2：天天爱跑步

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 9;
int n,m;
int w[N];
struct edge{
    int to,nex;
} e[N << 1];
int head[N],ecnt;
void addedge(int u,int v){
    ecnt++;
    e[ecnt] = (edge){v,head[u]};
    head[u] = ecnt;
}

int dep[N],w_ch[N],siz[N];
int fa[N];
void dfs1(int u,int father){
    siz[u] = 1;
    fa[u] = father;
    dep[u] = dep[fa[u]] + 1;
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to;
        if(v == fa[u])
            continue;
        dfs1(v,u);
        siz[u] += siz[v];
        if(siz[v] > siz[w_ch[u]])
            w_ch[u] = v;
    }
}
int w_top[N];
void dfs2(int u,int top){
    w_top[u] = top;
    if(w_ch[u]){
        dfs2(w_ch[u],top);
        for(int i = head[u];i;i = e[i].nex){
            int v = e[i].to;
            if(v == fa[u] || v == w_ch[u])
                continue;
            dfs2(v,v);
        }
    }
}

int LCA(int u,int v){
    while(w_top[u] != w_top[v]){
        if(dep[w_top[u]] < dep[w_top[v]])
            swap(u,v);
        u = fa[w_top[u]];
    }
    return (dep[u] < dep[v]) ? u : v;
}

vector<int> vec[N][4];
int cnt1[N << 1],cnt2[N << 1];
int ans[N];
void dfs3(int u){
    int tmp1 = cnt1[w[u] + dep[u]];
    int tmp2 = cnt2[w[u] - dep[u] + N];
    for(int i = head[u];i;i = e[i].nex){
        int v = e[i].to;
        if(v == fa[u])
            continue;
        dfs3(v);
    }
    int siz1 = vec[u][0].size(),siz2 = vec[u][1].size();
    int siz3 = vec[u][2].size(),siz4 = vec[u][3].size();

    for(int i = 0;i < siz1;i++)
        cnt1[vec[u][0][i]]++;
    for(int i = 0;i < siz2;i++)
        cnt1[vec[u][1][i]]--;

    for(int i = 0;i < siz3;i++)
        cnt2[vec[u][2][i] + N]++;
    for(int i = 0;i < siz4;i++)
        cnt2[vec[u][3][i] + N]--;

    ans[u] = (cnt1[w[u] + dep[u]] - tmp1) + (cnt2[w[u] - dep[u] + N] - tmp2);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i < n;i++){
        int u,v;
        cin >> u >> v;
        addedge(u,v);
        addedge(v,u);
    }
    dfs1(1,0);
    dfs2(1,0);
    for(int i = 1;i <= n;i++)
        cin >> w[i];
    for(int i = 1;i <= m;i++){
        int s,t;
        cin >> s >> t;
        int lca = LCA(s,t);
        vec[s][0].push_back(dep[s]);
        vec[fa[lca]][1].push_back(dep[s]);
        vec[t][2].push_back(dep[s] - (dep[lca] << 1));
        vec[lca][3].push_back(dep[s] - (dep[lca] << 1));
    }
    dfs3(1);
    for(int i = 1;i <= n;i++)
        cout << ans[i] << ' ';
    return 0;
}

【2.2】边差分

常用技巧——边权转点权。

可以把每条边的边权记录在其深度较大的点上，这样就可以做到一一对应，不会出现一个点对多条边的情况。

其余都是相同的，就是要注意修改点权不要修改 LCA（LCA 表示的边不在修改路径上），方法就是把点差分中在 LCA 父节点减的 1 移到 LCA 上，这样 LCA 就等于没加。

例题 1：闇の連鎖

如果一条主要边不在任何一个环上，那么切断它后切断任何一条辅助边都可以将 Dark 击败，对答案的贡献为 m。
如果一条主要边在 1 个环上，那么就必须切断在这个环上的 1 条辅助边（显然一个环上有且仅有 1 条辅助边），对答案的贡献为 1。
如果一条主要边在至少 2 个环上，那么切断它后无论如何都不能击败 Dark。

显然，辅助边 (u,v) 的作用是在原树上形成一个环，树上路径 u,v 经过的边都在这个环上，于是可以用边差分标记表示这些边所在环的数量加 1。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
struct edge{
    int to,nex;
} e[N << 1];
int ecnt,head[N];
int top[N],dep[N];
int fa[N],w_ch[N],siz[N];//每个节点的父节点、重儿子、子树大小 
void addedge(int u,int v){
    ecnt++;
    e[ecnt] = (edge){v,head[u]};
    head[u] = ecnt;
}
int val[N],val2[N];
int n,m,ans;
void dfs1(int cur,int father){
    fa[cur] = father;
    siz[cur] = 1;
    dep[cur] = dep[father] + 1;
    for(int i = head[cur];i;i = e[i].nex){
        int v = e[i].to;
        if(v != father){
            dfs1(v,cur);
            siz[cur] += siz[v];
            if(siz[v] > siz[w_ch[cur]])
                w_ch[cur] = v;
        }
    }
}
void dfs2(int cur,int link_top){
    top[cur] = link_top;
    if(w_ch[cur]){//有重儿子（不是叶节点） 
        dfs2(w_ch[cur],link_top);
        for(int i = head[cur];i;i = e[i].nex){
            int v = e[i].to;
            if(v != fa[cur] && v != w_ch[cur])
                dfs2(v,v);
        }
    }
}
int LCA(int u,int v){
    while(top[u] != top[v]){
        if(dep[top[u]] < dep[top[v]])
            swap(u,v);
        u = fa[top[u]];
    }
    return (dep[u] < dep[v]) ? u : v;
}

void dfs3(int cur){
    for(int i = head[cur];i;i = e[i].nex){
        int v = e[i].to;
        if(v != fa[cur]){
            dfs3(v);
            val[cur] += val[v];
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    for(int i = 1;i < n;i++){
        int u,v;
        cin >> u >> v;
        addedge(u,v);
        addedge(v,u);
    }
    dep[1] = 1;
    dfs1(1,-1);
    dfs2(1,-1);
    for(int i = 1;i <= m;i++){
        int u,v;
        cin >> u >> v;
        val[u]++;val[v]++;
        int lca = LCA(u,v);
        val[lca] -= 2;
    }
    dfs3(1);
    for(int i = 2;i <= n;i++){//根节点不表示任何一条边，不要把根节点算上了
        if(val[i] == 0)
            ans += m;
        if(val[i] == 1)
            ans++;
    }
    cout << ans;
    return 0;
}