: 割裂)
2025年3月GESP真题及题解(C++八级): 割裂
题目描述
小杨有一棵包含 $ n $ 个节点的树，其中节点的编号从 $ 1 $ 到 $ n $。
小杨设置了 $ a $ 个好点对{ ⟨ u 1 , v 1 ⟩ , ⟨ u 2 , v 2 ⟩ , … , ⟨ u a , v a ⟩ } \{\langle u_1, v_1 \rangle, \langle u_2, v_2 \rangle, \dots, \langle u_a, v_a \rangle\}{⟨u1,v1⟩,⟨u2,v2⟩,…,⟨ua,va⟩}和一个坏点对⟨ b u , b v ⟩ \langle b_u, b_v \rangle⟨bu,bv⟩。一个节点能被删除，当且仅当：
- 删除该节点后对于所有的 $ 1 \leq i \leq a $，好点对 $ u_i $ 和 $ v_i $ 仍然连通；
- 删除该节点后坏点对 $ b_u $ 和 $ b_v $ 不连通。
如果点对中的任意一个节点被删除，其视为不连通。
小杨想知道，还有多少个节点能被删除。
输入格式
第一行包含两个非负整数 $ n $, $ a $，含义如下题面所示。
接下来n − 1 n - 1n−1行，每行包含两个正整数 $ x_i, y_i $，代表存在一条连接节点 $ x_i $ 和 $ y_i $ 的边；
之后 $ a $ 行，每行包含两个正整数 $ u_i, v_i $，代表一个好点对 $ \langle u_i, v_i \rangle $；
最后一行包含两个正整数 $ b_u, b_v $，代表坏点对 $ \langle b_u, b_v \rangle $。
输出格式
输出一个非负整数，代表删除的节点个数。
输入输出样例 #1
输入 #1
6 2 1 3 1 5 3 6 3 2 5 4 5 4 5 3 2 6输出 #1
2说明/提示
| 子任务编号 | 分值 | $ n $ | $ a $ |
|---|---|---|---|
| 1 | 20 2020 | = 10 =10=10 | = 0 =0=0 |
| 2 | 20 2020 | $ \leq 100 $ | $ \leq 100 $ |
| 3 | 60 6060 | $ \leq 10^6 $ | $ \leq 10^5 $ |
对于全部数据，保证有 $ 1 \leq n \leq 10^6 $, $ 0 \leq a \leq 10^5 $, $ u_i \neq v_i $, $ b_u \neq b_v $。
思路分析
问题转化：
将原问题转化为：寻找树上所有满足以下条件的节点：- 在坏点对
(bu, bv)的路径上（包括端点）； - 不在任何一个好点对
(ui, vi)的路径上。
- 在坏点对
算法步骤：
- 读入树，并以节点1为根进行BFS，计算每个节点的深度、直接父节点和倍增祖先表（用于LCA查询）。
- 使用树上差分标记所有被好点对路径覆盖的节点：对于每个好点对
(u, v)，在其LCA处减1，在LCA的父节点处再减1，在u和v处加1。 - 通过逆BFS序累加差分值，得到每个节点被好点对路径覆盖的次数。
- 读入坏点对，计算其LCA。
- 遍历坏点对路径上的所有节点（从两端向上走到LCA），统计覆盖次数为0的节点个数，即为答案。
代码实现
#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e6+5;constintLOG=20;// 2^20 > 1e6vector<int>adj[MAXN];intdepth[MAXN];intparent[MAXN][LOG];// 倍增祖先，parent[u][0] 是直接父节点intdiff[MAXN];// 差分数组，最后变成覆盖次数vector<int>order;// BFS顺序intn,a;// 计算LCAintlca(intu,intv){if(depth[u]<depth[v])swap(u,v);// 将u提到与v同一深度for(inti=LOG-1;i>=0;--i){if(depth[parent[u][i]]>=depth[v]){u=parent[u][i];}}if(u==v)returnu;// 一起向上跳for(inti=LOG-1;i>=0;--i){if(parent[u][i]!=parent[v][i]){u=parent[u][i];v=parent[v][i];}}returnparent[u][0];}intmain(){scanf("%d%d",&n,&a);// 读入树边for(inti=0;i<n-1;++i){intx,y;scanf("%d%d",&x,&y);adj[x].push_back(y);adj[y].push_back(x);}// BFS预处理深度、倍增表，并记录BFS顺序queue<int>q;q.push(1);depth[1]=1;parent[1][0]=0;// 根的父亲设为0while(!q.empty()){intu=q.front();q.pop();order.push_back(u);// 计算倍增祖先for(inti=1;i<LOG;++i){parent[u][i]=parent[parent[u][i-1]][i-1];}for(intv:adj[u]){if(v==parent[u][0])continue;depth[v]=depth[u]+1;parent[v][0]=u;q.push(v);}}// 初始化diff为0memset(diff,0,sizeof(diff));// 处理好点对for(inti=0;i<a;++i){intu,v;scanf("%d%d",&u,&v);intl=lca(u,v);diff[u]++;diff[v]++;diff[l]--;if(l!=1){// 如果LCA不是根，还需要在其父节点减1diff[parent[l][0]]--;}}// 逆BFS序累加，得到每个节点的覆盖次数for(inti=order.size()-1;i>=0;--i){intu=order[i];intp=parent[u][0];if(p!=0){diff[p]+=diff[u];}}// 现在 diff[u] 表示节点 u 被好点对路径覆盖的次数// 读入坏点对intbu,bv;scanf("%d%d",&bu,&bv);intl_bad=lca(bu,bv);// 统计答案：坏点对路径上所有节点中，覆盖次数为0的节点个数intans=0;// 从 bu 向上走到 l_badintx=bu;while(x!=l_bad){if(diff[x]==0)ans++;x=parent[x][0];}// 从 bv 向上走到 l_badx=bv;while(x!=l_bad){if(diff[x]==0)ans++;x=parent[x][0];}// 检查 l_bad 本身if(diff[l_bad]==0)ans++;printf("%d\n",ans);return0;}功能分析
时间复杂度：
- 预处理BFS和倍增表：
O(n log n)。 - 处理
a个好点对：每次LCA查询O(log n)，共O(a log n)。 - 差分累加：
O(n)。 - 遍历坏点对路径：最坏
O(n)。 - 总时间复杂度：
O((n + a) log n)
- 预处理BFS和倍增表：
空间复杂度：
邻接表：
O(n)。深度、差分数组：
O(n)。倍增表：
O(n log n)，约80MB。BFS顺序数组：
O(n)。
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}
