夜雨聆风学习资料网

ARTICLE · 1370786

GESP 2025年3月 真题 割裂 完整题解(差分)

GESP 2025年3月 真题 割裂 完整题解(差分)
【GESP 2025年3月 真题 割裂 完整题解(差分)】
题目描述

小杨有一棵包含 n 个节点的树,其中节点的编号从 1 , n 。

小杨设置了 a 个好点对 { , ,… , } 和一对坏节点 . 一个节点能够被删除,当 且仅当:

  • 删除该节点后对于所有的 i(1 ≤i ≤a) ,好点对 uᵢ 和 vᵢ 仍然连通;
  • 删除该节点后坏点对 bᵤ 和 bᵥ 不连通。

如果点对中的任意一个节点被删除,其视为不连通。

小杨想知道,有多少个节点能够被删除。

样例
输入
6 2
1 3
1 5
3 6
3 2
5 4
5 4
5 3
2 6
输出
2
题解正文

这题光看代码容易绕进去,先找个生活里的比方,比方对了,代码就是照着抄。

这道题出自 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。

把比方里的动作换成代码里的语句,思路就完整了。

读入数据 → 递归处理子问题,回溯时汇总 → 按格式输出

比方和代码是一一对应的:比方里先说清「有几样东西」,对应代码里的变量;比方里「一个一个过」,对应那个循环。

四、完整代码

建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。

#include <bits/stdc++.h>
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();
}
五、比方和代码的对应关系

代码在上面,这里只挑最关键的两段讲,其他都是顺手写的。

第一段,把数据读进来。

    cin >> n >> k;

读入这段只要盯一件事:变量类型装不装得下。其他都可以照抄。

第二段,核心处理。

    for(auto v: e[u]){
        if(v == fa) continue;
        dfs2(v, u);
        g[u] += g[v];
        h[u] += h[v];
    }

这段是整道题唯一需要想的地方,也是差分的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。

六、手推一遍最踏实

代码写完不算完,得验。验也有顺序,从样例开始。

样例输入

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

样例输出

2

按这个顺序走一遍,跟上面那个比方对上:

  1. 跑题目给的样例,输出和样例逐字符一致,包括空格和换行。
  2. 把数据压到最少,边界情形下答案仍然对。
  3. 看最后一行,结尾有换行,不多输出空行。
七、比方失效的地方
容易错的地方错误写法正确写法
递归层数爆栈链状数据直接递归到 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)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料