图论与树形结构算法精解：Dijkstra、LCA与树形DP实战

1. 图论与树形结构算法精解

最近在准备8级算法考试，刷了不少图论和树形结构的题目。这些题目涵盖了Dijkstra、树形差分、LCA、倍增、树形DP等经典算法，对算法能力的提升很有帮助。下面我将详细解析这9道题目，分享解题思路和实现细节。

2. 题目详解与代码实现

2.1 P14923：无向图安全节点判断

问题分析： 给定一个无向图，每个节点有奶酪权值。猫在节点a，老鼠在节点b。判断哪些节点是"安全"的——即老鼠可以从该节点逃到b，且路径上每个点老鼠到达时间都严格小于猫到达时间。

核心思路：

1. 计算所有节点到b的最短距离dis_b[]
2. 计算所有节点到a的最短距离dis_a[]
3. 安全节点满足：dis_b[i] < dis_a[i]

算法选择： 使用Dijkstra算法计算单源最短路径，时间复杂度O((n+m)logn)

实现细节：

#include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+5; int n,m,a,b,ans,res[N],dis[N],vis[N]; vector<pair<int,int>> to[N]; struct Node{ int x,s; bool operator<(const Node& t)const{return t.s<s;} }; void dijkstra(int start){ priority_queue<Node> q; memset(dis,0x3f,sizeof dis); memset(vis,0,sizeof vis); q.push({start,0}); dis[start]=0; while(!q.empty()){ Node t=q.top(); q.pop(); if(vis[t.x]) continue; vis[t.x]=1; for(auto& [p,s]:to[t.x]){ if(dis[p]>dis[t.x]+s){ dis[p]=dis[t.x]+s; q.push({p,dis[p]}); } } } } signed main(){ cin>>n>>m>>a>>b; for(int i=1;i<=n;i++) cin>>res[i]; for(int i=1;i<=m;i++){ int x,y,z; cin>>x>>y>>z; to[x].emplace_back(y,z); to[y].emplace_back(x,z); } dijkstra(b); vector<int> dis_b(dis,dis+n+1); dijkstra(a); vector<int> dis_a(dis,dis+n+1); for(int i=1;i<=n;i++) if(dis_b[i]<dis_a[i]) ans+=res[i]; cout<<ans<<"\n"; }

注意事项：

1. 使用优先队列优化Dijkstra时，注意重载比较运算符的方向
2. 图可能很大，使用邻接表存储更节省空间
3. 初始化距离数组时要用足够大的值(0x3f3f3f3f)

2.2 P11967：树形差分处理点对连通性

问题分析： 给定一棵树，有a个好点对和1个坏点对。删除一个节点后，要求所有好点对仍连通，坏点对不连通。求可删除的节点数量。

核心思路：

1. 使用树形差分统计每个边被好点对路径覆盖的次数
2. 坏点对路径上的边必须恰好被覆盖a次
3. 统计满足条件的节点数量

算法选择： LCA+树形差分，时间复杂度O(nlogn + mlogn)

实现细节：

#include<bits/stdc++.h> using namespace std; const int N=1e6+5; int n,m,d[N],dp[N][25],dd[N],sum[N]; vector<int> to[N]; void dfs(int x,int fa){ d[x]=d[fa]+1; dp[x][0]=fa; for(int i=1;i<=20;i++) dp[x][i]=dp[dp[x][i-1]][i-1]; for(int y:to[x]){ if(y==fa) continue; dfs(y,x); } } int lca(int x,int y){ if(d[x]<d[y]) swap(x,y); for(int i=20;i>=0;i--) if(d[dp[x][i]]>=d[y]) x=dp[x][i]; if(x==y) return x; for(int i=20;i>=0;i--) if(dp[x][i]!=dp[y][i]) x=dp[x][i], y=dp[y][i]; return dp[x][0]; } void calc(int x,int fa){ sum[x]=dd[x]; for(int y:to[x]){ if(y==fa) continue; calc(y,x); sum[x]+=sum[y]; } } int main(){ cin>>n>>m; for(int i=1;i<n;i++){ int x,y; cin>>x>>y; to[x].push_back(y); to[y].push_back(x); } dfs(1,0); while(m--){ int x,y; cin>>x>>y; int w=lca(x,y); dd[x]++; dd[y]++; dd[w]--; dd[dp[w][0]]--; } int x,y; cin>>x>>y; calc(1,0); int w=lca(x,y), ans=0; while(true){ if(sum[x]==0) ans++; if(x==w) break; x=dp[x][0]; } while(true){ if(sum[y]==0) ans++; if(y==w) break; y=dp[y][0]; } if(sum[w]==0) ans--; cout<<ans<<"\n"; }

注意事项：

1. 树形差分时，要在LCA和其父节点处减1
2. 统计结果时要从两个端点向LCA遍历
3. LCA的预处理深度要足够(20层足够处理1e6规模的树)

2.3 P10289：带传送门的LCA最短路径

问题分析： n个节点的树，k个特殊城市可以互相瞬间传送。q次询问s到t的最短时间(走过一条边需要1单位时间)。

核心思路：

1. 计算s到t的原始距离 = d[s]+d[t]-2*d[lca(s,t)]
2. 计算通过传送门的最短距离 = min_dis[s] + min_dis[t]
3. 取两者较小值作为答案

算法选择： BFS预处理+k个源的BFS+LCA，时间复杂度O(nlogn + klogn + qlogn)

实现细节：

#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int n,k,Q,d[N],dis[N],fa[N][25]; vector<int> to[N]; void dfs(int x,int f,int dep){ d[x]=dep; fa[x][0]=f; for(int i=1;i<=20;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for(int y:to[x]){ if(y==f) continue; dfs(y,x,dep+1); } } void bfs(vector<int>& starts){ queue<int> q; memset(dis,0x3f,sizeof dis); for(int x:starts){ dis[x]=0; q.push(x); } while(!q.empty()){ int x=q.front(); q.pop(); for(int y:to[x]){ if(dis[y]>dis[x]+1){ dis[y]=dis[x]+1; q.push(y); } } } } int lca(int x,int y){ if(d[x]<d[y]) swap(x,y); for(int k=20;k>=0;k--) if(d[fa[x][k]]>=d[y]) x=fa[x][k]; if(x==y) return x; for(int k=20;k>=0;k--) if(fa[x][k]!=fa[y][k]) x=fa[x][k], y=fa[y][k]; return fa[x][0]; } int main(){ cin>>n>>k>>Q; for(int i=1;i<n;i++){ int x,y; scanf("%d%d",&x,&y); to[x].push_back(y); to[y].push_back(x); } dfs(1,0,1); vector<int> starts(k); for(int i=0;i<k;i++) cin>>starts[i]; bfs(starts); while(Q--){ int s,t; cin>>s>>t; int l=lca(s,t); int original=d[s]+d[t]-2*d[l]; int teleport=dis[s]+dis[t]; cout<<min(original,teleport)<<"\n"; } }

注意事项：

1. 多源BFS初始化时要把所有起点加入队列
2. LCA预处理时注意根节点的深度设为1
3. 两种距离计算方式都要考虑，取最小值

2.4 P10725：树形DP求异色节点最远距离

问题分析： 给定一棵树，每个节点是黑色或白色。求相距最远的一对不同颜色节点的距离。

核心思路：

1. 树形DP维护每个节点向下的最远白点和黑点距离
2. 在DFS过程中，用当前节点的最远白点+兄弟节点的最远黑点(或反之)更新答案
3. 注意处理单色树的情况

算法选择： 树形DP，时间复杂度O(n)

实现细节：

#include<bits/stdc++.h> using namespace std; const int N=1e5+5, INF=0x3f3f3f3f; int n,a[N],f[N][2],ans; vector<int> to[N]; void dfs(int x,int fa){ f[x][0]=f[x][1]=-INF; f[x][a[x]]=0; for(int y:to[x]){ if(y==fa) continue; dfs(y,x); // 更新答案：当前x的白+子节点y的黑 或 当前x的黑+子节点y的白 ans=max(ans, f[x][0]+f[y][1]+1); ans=max(ans, f[x][1]+f[y][0]+1); // 更新x的最远距离 f[x][0]=max(f[x][0], f[y][0]+1); f[x][1]=max(f[x][1], f[y][1]+1); } } int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<n;i++){ int x,y; cin>>x>>y; to[x].push_back(y); to[y].push_back(x); } dfs(1,0); cout<<(ans>0?ans:0)<<"\n"; // 处理全黑或全白的情况 }

注意事项：

1. 初始化f数组为负无穷，表示不可达
2. 只有当前颜色存在的节点才能更新答案
3. 处理全黑或全白树的情况，此时答案为0

2.5 P13019：倍增法处理树上移动

问题分析： 给定一棵有根树，q次旅行，每次从s出发，按照k个指令移动：正数表示向父节点移动指定步数，负数表示向最小编号子节点移动指定步数。求最终停留的节点。

核心思路：

1. 预处理每个节点向上和向下的倍增表
2. 对每个指令，使用倍增法快速跳跃
3. 注意处理超出树范围的情况

算法选择： 倍增法，预处理O(nlogn)，查询O(qlogn)

实现细节：

#include<bits/stdc++.h> using namespace std; const int N=1e5+5; vector<int> to[N]; int d[N],up[N][25],down[N][25],n,m; void dfs(int x,int fa){ d[x]=d[fa]+1; up[x][0]=(fa?fa:x); for(int i=1;i<=20;i++) up[x][i]=up[up[x][i-1]][i-1]; int mi=N; // 最小子节点编号 for(int y:to[x]){ if(y==fa) continue; dfs(y,x); mi=min(mi,y); } down[x][0]=(mi==N?x:mi); // 没有子节点则指向自己 for(int i=1;i<=20;i++) down[x][i]=down[down[x][i-1]][i-1]; } int main(){ cin>>n>>m; for(int i=2;i<=n;i++){ int x; cin>>x; to[x].push_back(i); } dfs(1,0); while(m--){ int x,y; cin>>x>>y; while(y--){ int z; cin>>z; if(z>0){ // 向上移动 for(int i=20;i>=0;i--){ if(z>=(1<<i)){ z-=(1<<i); x=up[x][i]; } } }else{ // 向下移动 z=-z; for(int i=20;i>=0;i--){ if(z>=(1<<i)){ z-=(1<<i); x=down[x][i]; } } } } cout<<x<<"\n"; } }

注意事项：

1. 预处理时，根节点的up表指向自己
2. 没有子节点时，down表也指向自己
3. 处理指令时要从高位到低位检查

2.6 P13020：树遍历序列计数

问题分析： 计算n个节点的树有多少种不同的DFS序，结果模1e9。

核心思路：

1. 对于固定根的情况，DFS序数量为各节点子节点数的阶乘的乘积
2. 考虑不同根的情况，需要乘以所有节点度数的乘积
3. 特判n=1的情况

数学推导： 对于固定根root，DFS序数量 = deg(root)! * ∏(deg(i)-1)! [i≠root] 对于所有根的情况，总数量 = ∏deg(i) * ∏(deg(i)-1)! * 2(n-1)

实现细节：

#include<bits/stdc++.h> using namespace std; const int MOD=1e9, N=1e5+5; long long n,fac[N],d[N],ans=1; int main(){ cin>>n; if(n==1){ cout<<"1\n"; return 0; } fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%MOD; for(int i=1;i<n;i++){ int x,y; cin>>x>>y; d[x]++; d[y]++; } for(int i=1;i<=n;i++){ ans=ans*fac[d[i]-1]%MOD; } ans=ans*2%MOD*(n-1)%MOD; cout<<ans<<"\n"; }

注意事项：

1. 阶乘预处理要足够大(n的范围)
2. 模运算要仔细，避免中间结果溢出
3. n=1时要特判输出1

2.7 P10726：挡板掉落时间计算

问题分析： n个水平挡板，各有高度和左右坐标。从s挡板左端出发到t挡板，移动和掉落都花费1单位时间。求最小时间。

核心思路：

1. 按高度排序挡板
2. DP[i][0/1]表示到达i挡板左/右端的最小时间
3. 从高到低转移，考虑从当前挡板左右端点掉落到下方挡板的情况

算法选择： 动态规划+排序，时间复杂度O(n^2)

实现细节：

#include<bits/stdc++.h> using namespace std; const int N=1e4+5; const long long INF=1e18; int n,s,t,ss,tt; long long dp[N][2],ans=INF; struct Board{ int l,r,h,id; bool operator<(const Board& b)const{return h>b.h;} }a[N]; int main(){ cin>>n>>s>>t; for(int i=1;i<=n;i++){ cin>>a[i].l>>a[i].r>>a[i].h; a[i].id=i; } sort(a+1,a+n+1); for(int i=1;i<=n;i++){ if(a[i].id==s) ss=i; if(a[i].id==t) tt=i; } memset(dp,0x3f,sizeof dp); dp[ss][0]=0; dp[ss][1]=a[ss].r-a[ss].l; for(int i=ss;i<=tt;i++){ // 向左下方掉落 for(int j=i+1;j<=tt;j++){ if(a[i].h<=a[j].h) continue; if(a[i].l>=a[j].l && a[i].l<=a[j].r){ long long cost=dp[i][0]+a[i].h-a[j].h; dp[j][0]=min(dp[j][0], cost+a[i].l-a[j].l); dp[j][1]=min(dp[j][1], cost+a[j].r-a[i].l); if(j==tt) ans=min(ans, cost); break; } } // 向右下方掉落 for(int j=i+1;j<=tt;j++){ if(a[i].h<=a[j].h) continue; if(a[i].r>=a[j].l && a[i].r<=a[j].r){ long long cost=dp[i][1]+a[i].h-a[j].h; dp[j][0]=min(dp[j][0], cost+a[i].r-a[j].l); dp[j][1]=min(dp[j][1], cost+a[j].r-a[i].r); if(j==tt) ans=min(ans, cost); break; } } } cout<<(ans==INF?-1:ans)<<"\n"; }

注意事项：

1. 挡板要按高度从高到低排序
2. 初始化DP数组为极大值
3. 处理无法到达的情况输出-1

2.8 P10264：卡牌消除的倍增优化

问题分析： n张牌排成一列，每张有点数。从前往后扫描，当遇到两张相同的牌时，移除它们之间的所有牌。多次询问区间[l,r]最终剩下的牌数。

核心思路：

1. 预处理每个位置i后面第一个与a[i]相同的位置nxt[i]
2. 使用倍增法预处理跳跃表dp[i][k]表示从i开始跳跃2^k次后的位置
3. 对每个查询，使用倍增法快速计算消除过程

算法选择： 倍增法，预处理O(nlogn)，查询O(qlogn)

实现细节：

#include<bits/stdc++.h> using namespace std; const int N=15e4+5; int T,n,a[N],dp[N][25],last[15]; int main(){ cin>>T; while(T--){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; // 初始化last数组 for(int i=1;i<=13;i++) last[i]=n+1; // 预处理nxt数组(用dp[i][0]表示) for(int i=n;i>=1;i--){ dp[i][0]=last[a[i]]; last[a[i]]=i; } // 预处理倍增表 for(int j=1;j<=20;j++){ for(int i=1;i<=n;i++){ if(dp[i][j-1]>n) dp[i][j]=n+1; else dp[i][j]=dp[dp[i][j-1]+1][j-1]; } } int q; cin>>q; while(q--){ int l,r; cin>>l>>r; int ans=0; while(l<=r){ bool found=false; for(int j=20;j>=0;j--){ if(dp[l][j]<=r){ l=dp[l][j]+1; found=true; break; } } if(!found){ ans++; l++; } } cout<<ans<<"\n"; } } }

注意事项：

1. 点数范围很小(1-13)，可以用数组代替map记录最后出现位置
2. 预处理时注意处理边界情况(n+1表示无法跳跃)
3. 查询时从高位到低位尝试跳跃

2.9 P14924：环形宝石分段的倍增解法

问题分析： n种宝石排成环，每种宝石有类型t[i]。要将环分成若干段，每段包含所有1~m类型。求最多可分多少段。

核心思路：

1. 破环为链，复制一遍数组
2. 预处理每个位置i作为左端点时，能覆盖所有类型的最右端点R[i]
3. 使用倍增法快速计算从每个位置开始最多能分多少段

算法选择： 滑动窗口+倍增法，时间复杂度O(nlogn)

实现细节：

#include<bits/stdc++.h> using namespace std; const int N=1e6+5; int n,m,a[N*2],dp[N*2][25],ans; int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; a[i+n]=a[i]; } memset(dp,0x3f,sizeof dp); int cnt[N]={0}, tot=0, r=0; // 滑动窗口预处理R[i](用dp[i][0]表示) for(int i=1;i<=2*n;i++){ while(tot<m && r<2*n){ r++; cnt[a[r]]++; if(cnt[a[r]]==1) tot++; } if(tot==m) dp[i][0]=r; cnt[a[i]]--; if(cnt[a[i]]==0) tot--; } // 预处理倍增表 for(int j=1;j<=20;j++){ for(int i=1;i<=2*n;i++){ if(dp[i][j-1]>2*n) dp[i][j]=2*n+1; else dp[i][j]=dp[dp[i][j-1]+1][j-1]; } } // 对每个起始位置计算最大分段数 for(int i=1;i<=n;i++){ int sum=0, l=i, r=i+n-1; for(int j=20;j>=0;j--){ if(dp[l][j]<=r){ sum+=(1<<j); l=dp[l][j]+1; } } ans=max(ans,sum); } cout<<ans<<"\n"; }

注意事项：

1. 数组要复制一倍处理环形问题
2. 滑动窗口时要动态维护当前窗口内的类型计数
3. 倍增预处理时注意处理边界情况

3. 算法总结与备考建议

通过这9道题的练习，我总结了以下算法要点和备考建议：

1. 图论算法：

   • Dijkstra算法适用于单源最短路径，优先队列优化版时间复杂度O((n+m)logn)
   • 多源BFS可以同时处理多个起点的最短路径问题
   • 邻接表是存储稀疏图的高效方式

2. 树形结构处理：

   • LCA(最近公共祖先)的倍增法预处理O(nlogn)，查询O(logn)
   • 树形差分是处理树上路径覆盖问题的有力工具
   • 树形DP通常需要后序遍历或DFS实现

3. 倍增法应用场景：

   • 处理大规模跳跃问题(如P13019的树上移动)
   • 优化区间查询问题(如P10264的卡牌消除)
   • 解决分段最值问题(如P14924的宝石分段)

4. 动态规划技巧：

   • 状态设计要完整覆盖问题所有可能情况
   • 转移方程要考虑所有可能的转移来源
   • 初始化要合理，边界条件要处理好

5. 环形问题处理：

   • 常用破环为链的方法，将数组复制一倍
   • 滑动窗口法可以高效处理连续区间问题

6. 编码注意事项：

   • 使用足够大的常量表示无穷大(如0x3f3f3f3f)
   • 模运算要注意中间结果可能溢出
   • 全局变量和局部变量要区分清楚，避免冲突

7. 调试技巧：

   • 对树类问题，可以打印出树结构辅助调试
   • 对DP问题，可以打印DP数组检查状态转移
   • 对边界情况(如n=1)要单独测试

在备考过程中，建议：

1. 分类刷题，掌握每类问题的核心算法
2. 总结常见解题模式和技巧
3. 注意时间复杂度的分析，避免超时
4. 多写多练，提高编码速度和准确性
5. 重视边界条件的测试

这些题目涵盖了8级考试中的典型算法和数据结构，理解并掌握这些解题思路对考试有很大帮助。在实际编程时，要注意代码的规范性和可读性，良好的编码习惯能减少调试时间。