LCA(最近公共祖先)与树上差分-海口c网

LCA(最近公共祖先)与树上差分

article/2025/8/5 0:30:20

LCA：

我们先看一道例题洛谷p3379

这道题就是LCA的模板题

LCA大抵有三种方法处理，我们这里只讲两种

分别是Tarjan和倍增法，也分别是离线和在线算法

我们这里先讲Tarjan

Tarjan：

一提到Tarjan这个名字，相信大家都能想到dfs

没错，这个方法就是利用dfs解决LCA的

TarjanTarjan算法的优点在于相对稳定，时间复杂度也比较居中，也很容易理解。

下面详细介绍一下TarjanTarjan算法的基本思路：

任选一个点为根节点，从根节点开始。
遍历该点u所有子节点v，并标记这些子节点v已被访问过。
若是v还有子节点，返回第2步，否则下一步。
合并v到u上。
寻找与当前点u有询问关系的点v。
若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。

为了合并两个点，我们可以使用并查集（也是Tarjan发明的）

相信大家都会

不会的可以看这篇文章

一篇讲解并查集的文章

CODE：

#include<bits/stdc++.h>
using namespace std;
int fa[(int)5e5+10],vis[(int)5e5+10],ans[(int)5e5+10],n,m,s,x,y,a,b;
vector<int> v[(int)5e5+10];
vector<pair<int,int>> ask[(int)5e5+10];
int find(int x){if(fa[x]==x) return x;return fa[x]=find(fa[x]);
}
void merge(int x,int y){if(find(x)!=find(y))fa[find(x)]=find(y);
}
void tarjan(int x){vis[x]=1;for(int i=0;i<v[x].size();i++){if(vis[v[x][i]])continue;tarjan(v[x][i]);merge(v[x][i],x);}for(int i=0;i<ask[x].size();i++)if(vis[ask[x][i].first]) ans[ask[x][i].second]=find(ask[x][i].first);
}int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m>>s;for(int i=1;i<=int(5e5+10);i++) fa[i]=i;for(int i=1;i<n;i++){cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}for(int i=1;i<=m;i++){cin>>a>>b;if(a==b)ans[i]=a;else{ask[a].push_back({b,i});ask[b].push_back({a,i});} }tarjan(s);for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}

好，这就是大名鼎鼎的Tarjan算法，时间复杂度O(n+question number)

比其他的LCA算法都要快，但是它是离线算法，有的时候就只能用倍增法了。

倍增法：

首先我们让深度更大的节点跳直至跟另一个节点深度一致，然后再一起跳，交汇的地方就是LCA。

问题1：怎么高效率地跳来跳去

答：预处理，就跟ST表一样，我们令parents[u][i], 是u结点的 $2^i$ 祖先结点。

然后进行dp就行了。

问题2：怎么知道跳到哪里？

答：直接倒着枚举

CODE：

#include <bits/stdc++.h>
using namespace std;
const int MAX = 5e5 + 10;
int n, m, s, f[MAX][20], dep[MAX];
vector<int> t[MAX];
void dfs(int u) {for (int i = 1; (1 << i) <= dep[u]; i++)f[u][i] = f[f[u][i - 1]][i - 1];for (int v : t[u]) {if (v == f[u][0]) continue;dep[v] = dep[u] + 1;f[v][0] = u;dfs(v);}
}
int LCA(int u, int v) {if (dep[u] < dep[v]) swap(u, v);for (int i = 19; i >= 0; i--)if (dep[u] - (1 << i) >= dep[v])u = f[u][i];if (u == v) return u;for (int i = 19; i >= 0; i--)if (f[u][i] != f[v][i])u = f[u][i], v = f[v][i];return f[u][0];
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m >> s;for (int i = 1; i < n; i++) {int x, y;cin >> x >> y;t[x].push_back(y);t[y].push_back(x);}dep[s] = 1;dfs(s);while (m--) {int x, y;cin >> x >> y;cout << LCA(x, y) << "\n";}
}

树上差分：

非常的简单，树上差分，顾名思义，在树上进行差分（废话）

这里只是讲一下基础的应用 ——点差分和边差分。

洛谷p3128

这一题就是点差分的模板题。

我们定义d[i]为点i的权值，那么若x到y有路线，为了使这条路线上的点都统计，那么d[x]++,d[y]++,d[lca(x,y)]--,d[father[lca(x,y)]]--，点u的经过次数就是以u为根的子树权值之和

如果知道了这个，那么这道题轻松就可以AC了

CODE：

#include <bits/stdc++.h>
using namespace std;
const int MAX=5e5+10;
int n,m,f[MAX][20],dep[MAX],d[MAX],ans[MAX],maxn=-1;
vector<int> t[MAX];
void dfs(int u){for(int i=1;(1<<i)<=dep[u];i++)f[u][i]=f[f[u][i-1]][i-1];for(int v:t[u])if(v!=f[u][0])dep[v]=dep[u]+1,f[v][0]=u,dfs(v);
}
int LCA(int u,int v){if(dep[u]<dep[v])swap(u,v);for(int i=19;i>=0;i--)if(dep[u]-(1<<i)>=dep[v])u=f[u][i];if(u==v)return u;for(int i=19;i>=0;i--)if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];return f[u][0];
}
void dfs_ans(int u){ans[u]=d[u];for(int v:t[u])if(v!=f[u][0])dfs_ans(v),ans[u]+=ans[v];maxn=max(maxn,ans[u]);
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cin>>n>>m;for(int i=1,x,y;i<n;i++)cin>>x>>y,t[x].push_back(y),t[y].push_back(x);dep[1]=1;dfs(1);for(int i=1,s,t,mid;i<=m;i++)cin>>s>>t,mid=LCA(s,t),d[s]++,d[t]++,d[mid]--,f[mid][0]?d[f[mid][0]]--:0;dfs_ans(1);cout<<maxn;
}

那么边差分怎么处理呢？

处理边有一点复杂，不妨处理点。把所有的边全部都下移，把边的权值存到点上。

即若x到y有一条边，那么若dep[x]>dep[y]，那么这条边的权值就存在x上，否则就存在y上。

d[i]为i到father[i]的边的权值。若x到y有路线，d[x]+=1,d[y]+=1,d[lca(x,u)]-=2，i到f[i]的边的被覆盖次数就为以i为根的子树的权值之和。

相信看了以上的讲解，你肯定会做这道题了——洛谷p6869

这道题要在模板的基础上加上一点点微小的微不足道的微乎其微的修改就行了

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N=200003;
long long n, x[N], y[N], f[N][21], len[N], lg[N], lm, va1[N], va2[N], ans[N], an;
vector<int> ed[N], le[N];
void dfs(int w, int fa) {f[w][0] = fa;len[w] = len[fa] + 1;lm = max(lm, len[w]);le[len[w]].push_back(w);for (int i = 1; i <= lg[len[w]]; ++i)f[w][i] = f[f[w][i - 1]][i - 1];for (int i = 0; i < ed[w].size(); ++i)if (ed[w][i] != fa)dfs(ed[w][i], w);
}
int lca(int x, int y) {if (len[x] < len[y])swap(x, y);while (len[x] > len[y])x = f[x][lg[len[x] - len[y]] - 1];if (x == y)return x;for (int i = lg[len[x]] - 1; i >= 0; --i) if (f[x][i] != f[y][i])x = f[x][i], y = f[y][i];return f[x][0];
}
int main() {ios::sync_with_stdio(0);cin.tie(0);cin >> n;for (int i = 1; i < n; ++i) {cin >> x[i] >> y[i] >> va1[i] >> va2[i];ed[x[i]].push_back(y[i]);ed[y[i]].push_back(x[i]);}for (int i = 1; i <= n; ++i)lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);dfs(1, 0);for (int i = 1; i < n; ++i) {ans[i]++;ans[i + 1]++;ans[lca(i, i + 1)] -= 2;}for (int i = lm; i > 1; --i)for (int j = 0; j < le[i].size(); ++j)ans[f[le[i][j]][0]] += ans[le[i][j]];for (int i = 1; i < n; ++i) {long long as = len[x[i]] > len[y[i]] ? ans[x[i]] : ans[y[i]];an += (as * va1[i] < va2[i]) ? as * va1[i] : va2[i];}cout << an;
}

如果你做了这些题目还不满足的话，可以尝试做一下这几道题。

洛谷p3398

洛谷p3258

洛谷p1967

洛谷p1084

洛谷p2783

洛谷p2597

洛谷p2680

洛谷p1600

洛谷p1081