前言:
蓝桥杯前没有学到LCA，最后两题都用到了LCA。
无奈啊，今天补上这个
概述:
LCA即在一棵树上，找到两个结点的最近祖先(祖先可能有多个)。
主要有两种算法解决，这里讲解一下倍增dp算法找到LCA。
其基本思想是通过预处理出每个节点距离2^k个祖先的信息，并利用这些信息在查询时快速跳转到两个节点的同一深度，然后再沿着祖先链进行比较，找到它们的LCA。
具体来说，倍增LCA算法分为两个步骤：预处理和查询。预处理阶段需要对整棵树进行遍历，计算出每个节点距离2^k个祖先的距离信息。查询阶段则利用这些信息，在O(logn)的时间内找到两个节点的LCA。
在预处理阶段，我们可以使用动态规划的方式，逐层计算出节点距离2^k个祖先的距离信息。具体来说，设f[i][j]表示节点i距离2^j个祖先的距离，那么有以下递推式：
1
2
| f[i][0] = fa[i]
f[i][j] = f[f[i][j-1]][j-1] + f[i][j-1]
|
其中fa[i]表示节点i的父亲节点。可以看出，f[i][j]可以由f[i][j-1]和f[f[i][j-1]][j-1]计算得到。这也就是“倍增”的含义。通过这个递推式，我们可以在O(nlogn)的时间内预处理出所有节点距离2
预处理
利用深搜处理这颗树，然后预处理每个节点的倍增数组
1
2
3
4
5
6
7
8
| void dfs(int u,int fa){
f[u][0]=fa,dep[u]=dep[fa]+1;
for(int i=1;(1<<i)<=dep[u];i++)f[u][i]=f[[f[u][i-1]]][i-1];
for(auto &p:e[u]){
if(p!=fa)
dfs(p,u);
}
}
|
查询
让深度大的结点向上跳跃(这里的跳跃是大跳跃)，直到同一深度。
然后两者同时跳,直到跳到同一结点结束(注意该节点不是LCA，应该是该节点的上面的第一个祖先才是LCA)
1
2
3
4
5
6
7
8
9
10
11
| int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);//挑选深度更大的结点先跳跃
for(int i=20;i>=0;i--){
if(dep[f[u][i]]>=dep[v])u=f[u][i];//判断是否同一深度
}
if(u==v)return u;//如果用一深度
for(int i=20;i>=0;i--){
if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
}
return f[u][0];
}
|
树上差分
讲完lca，这里补充一下树上差分。
任意树上两个结点的距离会等于$distance=dist[u]+dist[v]-2*lca(u,v)
即从根到u结点的距离+根到v结点的距离-2*根到二者lca的距离(画图秒懂)
实战
接下来直接上两道蓝桥杯真题，快速掌握lca以及树上差分
给定一棵由 n 个结点组成的树以及 m 个不重复的无序数对 (a1, b1), (a2, b2),. . . , (am, bm)，
其中 ai 互不相同，bi 互不相同，ai ≠ bj(1 ≤ i, j ≤ m)。
小明想知道是否能够选择一条树上的边砍断，使得对于每个 (ai , bi) 满足 ai和 bi 不连通，
如果可以则输出应该断掉的边的编号（编号按输入顺序从 1 开始），否则输出 -1.(完整题目点题目就可以)
代码实现:
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
49
50
51
|
using namespace std;
const int N=1e5+5;
vector<pair<int,int>>e[N];
int dep[N],f[N][20],s[N],n,m,ans=-1;
void init(int u,int fa){
dep[u]=dep[fa]+1;f[u][0]=fa;
for(int i=1;(1<<i)<=dep[u];i++)f[u][i]=f[f[u][i-1]][i-1];
for(auto &p:e[u]){
if(p.first!=fa){
init(p.first,u);
}
}
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=20;i>=0;i--)
if(dep[f[u][i]]>=dep[v])u=f[u][i];
if(u==v)return u;
for(int i=20;i>=0;i--)
if(f[u][i]!=f[v][i])
u=f[u][i],v=f[v][i];
return f[u][0];
}
void dfs(int u,int fa){
for(auto &p:e[u]){
if (p.first!=fa) {
dfs(p.first, u);
s[u] += s[p.first];
if (s[p.first] == m)
ans = max(ans, p.second);
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
e[u].push_back({v,i});
e[v].push_back({u,i});
}
init(1,0);
for(int i=1;i<=m;i++){
int u,v;cin>>u>>v;
s[u]+=1;s[v]+=1;s[lca(u,v)]-=2;
}
dfs(1,0);
cout<<ans;
return 0;
}
|
某景区一共有 N 个景点，编号 1 到 N。景点之间共有 N − 1 条双向的摆渡车线路相连，形成一棵树状结构。在景点之间往返只能通过这些摆渡车进行，需要花费一定的时间。
小明是这个景区的资深导游，他每天都要按固定顺序带客人游览其中 K 个景点：A1, A2, . . . , AK。今天由于时间原因，小明决定跳过其中一个景点，只带游客按顺序游览其中 K − 1 个景点。具体来说，如果小明选择跳过 Ai，那么他会按顺序带游客游览 A1, A2, . . . , Ai−1, Ai+1, . . . , AK, (1 ≤ i ≤ K)。
请你对任意一个 Ai，计算如果跳过这个景点，小明需要花费多少时间在景点之间的摆渡车上？(具体见题目)
代码实现:
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
|
using namespace std;
typedef long long ll;
const int N=1e5+5;
vector<pair<int,int>>e[N];
ll dep[N],f[N][21];
ll dist[N];
void dfs(int u,int fa,ll d){
dep[u]=dep[fa]+1,f[u][0]=fa,dist[u]=d;
for(int i=1;(1<<i)<=dep[u];i++)f[u][i]=f[f[u][i-1]][i-1];
for(auto &p:e[u])
if(p.first!=fa)
dfs(p.first,u,d+p.second);
}
int lca(int u,int v){
if(dep[u]<dep[v])swap(u,v);
for(int i=20;i>=0;i--)
if(dep[f[u][i]]>=dep[v])u=f[u][i];
if(u==v)return u;
for(int i=20;i>=0;i--)
if(f[u][i]!=f[v][i])u=f[u][i],v=f[v][i];
return f[u][0];
}
ll get(int u,int v){
return dist[u]+dist[v]-2*dist[lca(u,v)];
}
int main(){
int n,k;cin>>n>>k;
for(int i=1;i<n;i++){
int u,v,t;cin>>u>>v>>t;
e[u].push_back({v,t});
e[v].push_back({u,t});
}
vector<int>a(k);
for(auto&p:a)cin>>p;
dfs(1,0,0);
ll sum=0;
for(int i=1;i<k;i++)sum+=get(a[i-1],a[i]);
for(int i=0;i<k;i++){
ll ans=sum;
if(i!=0)ans-=(get(a[i],a[i-1]));
if(i!=k-1)ans-=(get(a[i],a[i+1]));
if(i!=0&&i!=k-1)ans+=get(a[i-1],a[i+1]);
cout<<ans<<" ";
}
return 0;
}
|
