记录162#includebits/stdc.h // 引入万能头文件包含所有常用的标准库 using namespace std; // 使用标准命名空间 int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭cin与stdio的同步加快输入输出速度 cin.tie(0); // 解除cin与cout的绑定进一步加快IO效率 int t; // 定义变量t表示数据的组数 cint; // 输入数据组数t while(t--){ // 循环处理每一组测试数据 int n; // 定义变量n表示当前这组数据树的节点总数 cinn; // 输入节点数n if(n1){ // 特判如果只有一个节点不需要任何操作 cout0\n; // 输出0 continue; // 跳过当前循环处理下一组数据 } vectorint degree(n1,0); // 定义度数组用vector动态分配degree[i]记录节点i的度数初始化为0 for(int i1;in-1;i){ // 循环n-1次读入树的每一条边 int u, v; // 定义临时变量u和v代表一条边连接的两个节点 cinuv; // 输入一条边的两个端点 degree[u]; // 节点u的度数加1 degree[v]; // 节点v的度数加1 } int leaf_count0; // 定义变量leaf_count用来统计叶子节点度数为1的节点的总数 for(int i1;in;i){ // 遍历从1到n的每一个节点 if(degree[i]1){ // 如果当前节点的度数为1说明它是叶子节点 leaf_count; // 叶子节点计数加1 } } // 根据结论最少操作次数 叶子节点数量 - 1 coutleaf_count-1\n; // 输出最终答案 } return 0; // 主函数正常结束返回0 }题目传送门https://www.luogu.com.cn/problem/P13555前言我是一名专注信奥赛GESP、CSP-J/S的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的图论树的性质与数学推导问题。问题转化树与叶子节点题目给出了一个包含 n 个节点的树。每次操作选择一个根节点会在所有祖先-后代节点对之间连边。如果我们把树看作一个图那么一次操作实际上是把以该节点为根时树上所有的“祖先-后代”路径都覆盖上了绳子。通过数学推导和观察可以发现要让树上所有的节点对都被覆盖最少需要的操作次数与树的叶子节点数量直接相关。算法设计统计叶子节点在树中叶子节点是指度数为 1 的节点只有一个邻居。根据本题的结论最少操作次数等于叶子节点的数量减去 1。因此我们的算法非常简单读入所有的边统计每个节点的度数最后数一数度数为 1 的节点有多少个将其减 1 输出即可。代码分块详细解释1. 头文件、IO 优化与变量定义#includebits/stdc.h // 引入万能头文件包含所有常用的标准库 using namespace std; // 使用标准命名空间 int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭cin与stdio的同步加快输入输出速度 cin.tie(0); // 解除cin与cout的绑定进一步加快IO效率 int t; // 定义变量t表示数据的组数 cint; // 输入数据组数t详细分析由于题目中数据组数 tt 最大可达 2×10^4 总节点数 ∑n≤2×10^5 输入输出量较大因此必须加上ios::sync_with_stdio(false);和cin.tie(0);进行 IO 加速防止程序因 IO 瓶颈超时。2. 边界处理与树的读入while(t--){ // 循环处理每一组测试数据 int n; // 定义变量n表示当前这组数据树的节点总数 cinn; // 输入节点数n if(n1){ // 特判如果只有一个节点不需要任何操作 cout0\n; // 输出0 continue; // 跳过当前循环处理下一组数据 } vectorint degree(n1,0); // 定义度数组用vector动态分配degree[i]记录节点i的度数初始化为0 for(int i1;in-1;i){ // 循环n-1次读入树的每一条边 int u, v; // 定义临时变量u和v代表一条边连接的两个节点 cinuv; // 输入一条边的两个端点 degree[u]; // 节点u的度数加1 degree[v]; // 节点v的度数加1 }详细分析边界特判当 n1n1 时树上只有一个节点不存在任何节点对因此不需要操作直接输出 0。度数统计使用vectorint degree(n1, 0)动态分配度数组节省内存。对于树来说有 n 个节点就有 n−1n−1 条边。每读入一条边 (u,v) 就将 u 和 v 的度数各加 1。3. 核心逻辑统计叶子节点与输出答案int leaf_count0; // 定义变量leaf_count用来统计叶子节点度数为1的节点的总数 for(int i1;in;i){ // 遍历从1到n的每一个节点 if(degree[i]1){ // 如果当前节点的度数为1说明它是叶子节点 leaf_count; // 叶子节点计数加1 } } // 根据结论最少操作次数 叶子节点数量 - 1 coutleaf_count-1\n; // 输出最终答案 } return 0; // 主函数正常结束 }详细分析叶子节点判定遍历所有节点如果degree[i] 1说明该节点只与一个节点相连即为叶子节点。输出答案根据图论推导最少操作次数为leaf_count - 1。例如样例 1 中叶子节点为 1 和 3共 2 个答案为 2−11 样例 2 中叶子节点为 2, 3, 5共 3 个答案为 3−12。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点IO 加速ios::sync_with_stdio(false)关闭 C 与 C 标准流同步应对 2×1052×105 级别的大量输入输出防止超时边界特判if(n1)单独处理只有一个节点的情况避免 n1n1 时叶子节点数为 1导致输出 0 的逻辑错误度数统计degree[u]; degree[v]读入边时同步更新两端点的度数无需真正建树仅通过度数即可获取树的结构信息叶子节点统计if(degree[i]1)遍历所有节点统计度数为 1 的节点数找到了决定最少操作次数的关键变量公式输出cout leaf_count-1应用推导出的数学结论将复杂的图论问题转化为简单的数学计算时间复杂度仅为 O(n)O(n)
