题解：洛谷 P1670 [USACO04DEC] Tree Cutting S

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1670 [USACO04DEC] Tree Cutting S - 洛谷【题目描述】约翰意识到贝茜建设网络花费了他巨额的经费就把她解雇了。贝茜很愤怒打算狠狠报复。她打算破坏刚建成的约翰的网络。约翰的网络是树形的连接着N NN个牛棚。她打算切断某一个牛棚的电源使和这个牛棚相连的所有电缆全部中断。之后就会存在若干子网络。为保证破坏够大每一个子网的牛棚数不得超过总牛棚数的一半那哪些牛棚值得破坏呢【输入】第1 11行一个整数N NN。第2 22到N NN行每行输入两个整数表示一条电缆的两个端点。【输出】按从小到大的顺序输出所有值得破坏的牛棚。如果没有一个值得破坏就输出NONE。【输入样例】10 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10 3 8【输出样例】3 8【算法标签】#普及 #树形DP【代码详解】#includebits/stdc.husingnamespacestd;constintN10005,MN*2;intn;// n: 节点数inth[N],e[M],ne[M],idx;// 邻接表存储树intsiz[N],maxP[N];// siz: 子树大小maxP: 最大子树大小boolok[N],flag;// ok: 标记节点是否是重心flag: 标记是否有重心voidadd(inta,intb){e[idx]b,ne[idx]h[a],h[a]idx;}// 第一次DFS计算每个节点的子树大小voiddfs_1(intu,intfa){siz[u]1;// 初始化子树大小为1自身for(intih[u];i!-1;ine[i])// 遍历u的所有子节点{intve[i];// 子节点vif(vfa)// 跳过父节点continue;dfs_1(v,u);// 递归计算子节点的子树大小siz[u]siz[v];// 累加子节点的子树大小}}// 第二次DFS计算每个节点的最大子树大小并判断是否是重心voiddfs_2(intu,intfa){maxP[u]n-siz[u];// 考虑u的父节点方向的子树大小for(intih[u];i!-1;ine[i])// 遍历u的所有子节点{intve[i];// 子节点vif(vfa)// 跳过父节点continue;dfs_2(v,u);// 递归计算子节点的最大子树大小maxP[u]max(maxP[u],siz[v]);// 更新最大子树大小}if(maxP[u]n/2)// 如果最大子树大小不超过n/2则是重心ok[u]true;}intmain(){cinn;// 输入节点数memset(h,-1,sizeof(h));// 初始化邻接表for(inti1;in;i)// 输入n-1条边{intu,v;cinuv;add(u,v),add(v,u);// 添加无向边}dfs_1(1,0);// 第一次DFS计算子树大小dfs_2(1,0);// 第二次DFS判断重心for(inti1;in;i)// 遍历所有节点if(ok[i])// 如果节点i是重心{coutiendl;// 输出重心编号flagtrue;// 标记有重心}if(!flag)// 如果没有找到重心coutNONEendl;// 输出NONEreturn0;}【运行结果】10 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10 3 8 3 8