ARTICLE · 1370786
GESP 2025年3月 真题 割裂 完整题解(差分)
小杨有一棵包含 n 个节点的树,其中节点的编号从 1 , n 。
小杨设置了 a 个好点对 { , ,… , } 和一对坏节点 . 一个节点能够被删除,当 且仅当:
- 删除该节点后对于所有的 i(1 ≤i ≤a) ,好点对 uᵢ 和 vᵢ 仍然连通;
- 删除该节点后坏点对 bᵤ 和 bᵥ 不连通。
如果点对中的任意一个节点被删除,其视为不连通。
小杨想知道,有多少个节点能够被删除。
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6
这题光看代码容易绕进去,先找个生活里的比方,比方对了,代码就是照着抄。
这道题出自 GESP 2025年3月,八级的差分题。它不难,但每年都有人在这里丢分,丢的地方还都一样。我们花十分钟把它从头捋一遍。
题目:割裂
场次:2025年3月 八级|难度:八级
知识点:最近公共祖先 差分 倍增
链接:https://www.acgo.cn/problemset/info/75435
小杨有一棵包含 n 个节点的树,其中节点的编号从 1 , n 。 小杨设置了 a 个好点对 { , ,… , } 和一对坏节点 . 一个节点能够被删除,当 且仅当: - 删除该节点后对于所有的 i(1 ≤i ≤a) ,好点对 uᵢ 和 vᵢ 仍然连通; - 删除该节点后坏点对 bᵤ 和 bᵥ 不连通。 如果点对中的任意一个节点被删除,其视为不连通。 小杨想知道,有多少个节点能够被删除。
一句话概括:用最近公共祖先 差分 倍增把题目要求原样翻译成代码,属于考场上必须拿满分的题。
前提一,容器够不够大。题干没给明确范围,这类题的经验是:数据上千就用 long long,多占 4 个字节,换一个不出错。
前提二,两头有没有照顾到。最小规模先想一遍:n 等于 1 时程序会不会崩、答案是不是 0,这两种情况出题人最爱设陷阱。
前提三,交出去的样子对不对。第三件,最后注意输出格式。题目要几行就几行,行内空格几个就是几个,行末的换行别丢——算法对了格式错了,一样判错,这分丢得最冤。
先说这个比方。差分像记账时的「改一笔」:只在开头记「加 v」,在结束的下一位记「减 v」,最后从头加一遍,等于那段区间每笔都加了 v。
把比方里的动作换成代码里的语句,思路就完整了。
比方和代码是一一对应的:比方里先说清「有几样东西」,对应代码里的变量;比方里「一个一个过」,对应那个循环。
建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。
using namespace std;
const int N = 1e6+10;
int n, k;
vector<int> e[N];
int f[N][25], dep[N], g[N], h[N];
void dfs(int u, int fa){
dep[u] = dep[fa] + 1;
f[u][0] = fa;
for(int i = 1; i <= 20; i++){ // 遍历
f[u][i] = f[f[u][i - 1]][i - 1];
}
for(auto v: e[u]){ // 遍历
if(v == fa) continue; // 判断
dfs(v, u);
}
}
int lca(int u, int v){
if(dep[u] < dep[v]) swap(u, v); // 判断
int t = dep[u] - dep[v];
for(int i = 0; i <= 20; i++){ // 遍历
if(t & (1 << i)) u = f[u][i]; // 判断
}
for(int i = 20; i >= 0; i--){ // 遍历
if(f[u][i] != f[v][i]) u = f[u][i], v = f[v][i]; // 判断
if(u == v) return u; // 判断
}
return f[u][0];
}
int ans;
void dfs2(int u, int fa){
for(auto v: e[u]){ // 遍历
if(v == fa) continue; // 判断
dfs2(v, u);
g[u] += g[v];
h[u] += h[v];
}
if(!g[u] && h[u]) { // 判断
ans++;
}
}
void solve(){
cin >> n >> k; // 读入
for(int i = 1; i < n; i++){ // 遍历
int u, v;
cin >> u >> v; // 读入
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, 0);
for(int i = 1; i <= k; i++){ // 遍历
int u, v;
cin >> u >> v; // 读入
int lc = lca(u, v);
g[u]++, g[v]++, g[lc]--, g[f[lc][0]]--;
}
int u, v;
cin >> u >> v; // 读入
int lc = lca(u, v);
h[u]++, h[v]++, h[lc]--, h[f[lc][0]]--;
dfs2(1, 0);
cout << ans << '\n'; // 输出
}
int main(){
solve();
}
代码在上面,这里只挑最关键的两段讲,其他都是顺手写的。
第一段,把数据读进来。
读入这段只要盯一件事:变量类型装不装得下。其他都可以照抄。
第二段,核心处理。
if(v == fa) continue;
dfs2(v, u);
g[u] += g[v];
h[u] += h[v];
}
这段是整道题唯一需要想的地方,也是差分的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。
代码写完不算完,得验。验也有顺序,从样例开始。
样例输入
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6
样例输出
按这个顺序走一遍,跟上面那个比方对上:
- 跑题目给的样例,输出和样例逐字符一致,包括空格和换行。
- 把数据压到最少,边界情形下答案仍然对。
- 看最后一行,结尾有换行,不多输出空行。
| 容易错的地方 | 错误写法 | 正确写法 |
|---|---|---|
| 递归层数爆栈 | 链状数据直接递归到 n 层 | 改显式栈,或把递归改成从底往上推 |
| 累加结果溢出 | int sum = 0; | 累加变量用 long long |
| 输出格式不符 | cout << ans; | cout << ans << "\n"; |
| 多组数据没清空 | 全局数组直接用 | 每组数据前 memset 或重新赋值 |
这题的经验压缩成三行,考前扫一眼就够。
- 这题考的:最近公共祖先 差分 倍增——把题目条件一句一句翻译成代码,不添不减。
- 要记住的:区间加 v 就是
d[l] += v、d[r+1] -= v,最后跑一遍前缀和还原。 - 下一步:拿同场次另一道题练手,换题型不换节奏,手感就稳了。
下一篇继续同场次的真题。有更短的写法,欢迎评论区贴出来。
- 本文属于《GESP 真题题解》系列,第 93 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
- 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
- 想跟完整系列的朋友点个关注,更新会第一时间推送。
- 本系列合集目录(按年份/组别排序)
GESP 的坑多半在边界和读题上。这道差分题把该注意的点都列在上面的表里了,提交前逐条过一遍。
今天想问你:这道题你第一次交是 WA 还是 AC?卡在哪一步,评论区说说,我帮你看看。
顺手点个 赞,你的反馈决定我先把哪个专题更完;关注之后,每天的新题解会自动找上门。
想要这题的可运行代码文件?后台回复 “资料” 直接拿。
本篇编号 GESP-049(公众号 MP-049)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。















































































