GESP C++ 八级真题题解（2026年9月）

官方真题下载：复制下面这行网址，到手机或电脑浏览器打开，即可查看并下载官方真题试卷PDF：

https://gesp.ccf.org.cn/101/attach/1767258921631776.pdf

第1题：生成树计数

【题目描述】

给定一张  个点、 条边的无向连通图，满足：

• 每条边至多属于一个简单环（这样的图叫仙人掌图）；
• 没有重边和自环。

求这张图不同生成树的数量。两棵生成树不同，当且仅当存在一条边在一棵里出现、而在另一棵里不出现。答案对 998244353 取模。

【输入格式】

第一行 ；接下来  行每行  表示一条无向边（）。

【输出格式】

一行一个整数，生成树数量对 998244353 取模。

【样例 1】

输入：

7 8
1 2
2 3
3 1
3 4
4 5
5 6
6 7
7 4

输出：

12

【样例 2】

输入：

5 4
1 2
1 3
2 4
2 5

输出：

1

样例 2 只有  条边，本身就是一棵树、没有环，生成树唯一（就是它自己），答案为 1。

【思路分步推导】

第一步：先认清“仙人掌”长什么样

仙人掌的关键约束是任意一条边最多只属于一个环。于是一个个环之间只能通过“桥（不在任何环里的边）”相连，或者只共用一个点，绝不会共用一条边。下图左边是仙人掌，右边就是反例：

第二步：每个环要删恰好一条边，桥必须全保留

生成树要求连通全部点、恰好  条边且无环。对仙人掌：

• 一个长度为  的环，要破掉它就必须删掉环里恰好一条边（删多了会断、删少了还有环），共  种删法；
• 桥不在任何环上，一旦删掉图就不连通，所以桥一条都不能删，只有 1 种。

第三步：各环独立选择，答案连乘

不同的环互不共用边，删哪条边彼此独立，按乘法原理把每个环的长度乘起来即可。下图用样例 1 演示：三环 3 种、四环 4 种、桥必留，：

第四步：DFS 用“回边深度差”找环长

DFS 树中，当从  遇到一条指向已访问祖先  的回边时，这条回边与树上  的路径恰好围成一个环，环长为两端深度差加 1：

只在 dep[v] < dep[u]（从深点回到浅祖先）时统计一次，避免无向边来回算两遍。

【两种解法对比】

【参考代码】（DFS 深度差找环）

第2题：末班车

【题目描述】

城市有  个地铁站、 条单向线路。第  条线路从  驶向 ，最晚发车时间为 ，行驶耗时 。从第 0 到第  分钟每分钟都有一班车，第  分钟发车的车在第  分钟到达；乘客到达某站后，可以换乘该站“到达时刻及之后”发出的任意线路。

共  组询问：第  分钟从  站出发，能否到达  站？能则输出 Yes，否则 No，注意大小写。

【输入格式】

第一行 ；接下来  行每行 ；接下来  行每行 。

【输出格式】

 行，每行 Yes 或 No。

【数据范围】

，，，，。

【样例】

输入：

3 4 5
1 2 3 3
2 3 5 2
3 1 4 1
1 3 0 6
1 3 2
2 1 2
2 1 3
3 2 2
3 2 3

输出：

Yes
Yes
No
Yes
No

例如询问 ：2 点 2 分上车，乘 2→3（最晚 5、耗时 2）第 4 分到 3，正好赶上 3→1（最晚 4、耗时 1），能到，输出 Yes；而  到 3 已是第 5 分，赶不上 3→1 的末班车（最晚 4），输出 No。

【思路分步推导】

第一步：换个问法——求“最晚出发时间”

正向模拟“ 出发能不能到”要处理大量班次、且  高达 ，逐问搜索必超时。反过来预处理：对固定终点 ，定义  = 为了最终能到 ，从  出发最晚不能迟于第几分钟。于是询问  能到达当且仅当：

第二步：在反向图上转移

把每条边反向。已知当前点  的最晚时间是 ，原图有边 （最晚发车 、耗时 ），要赶上这趟车，从  出发的最晚时刻是“留出  分钟车程、且不晚于末班车 ”：

第三步：大根堆 Dijkstra 求最优

“最晚出发时间”越大越优，且每次取当前值最大的点去松弛别人，这正是 Dijkstra 的结构——把普通最短路的小根堆换成 priority_queue 大根堆、加法换成上面的  即可。对每个终点  各跑一次（共  次），之后每次询问 ：

【两种解法对比】

【满分参考代码】反向图 + priority_queue 大根堆 Dijkstra

【部分分参考代码】每次询问正向 DFS（ 小时可拿 40%）