题解：洛谷 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

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=10005,M=N*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(inti=h[u];i!=-1;i=ne[i])// 遍历u的所有子节点{intv=e[i];// 子节点vif(v==fa)// 跳过父节点continue;dfs_1(v,u);// 递归计算子节点的子树大小siz[u]+=siz[v];// 累加子节点的子树大小}}// 第二次DFS，计算每个节点的最大子树大小，并判断是否是重心voiddfs_2(intu,intfa){maxP[u]=n-siz[u];// 考虑u的父节点方向的子树大小for(inti=h[u];i!=-1;i=ne[i])// 遍历u的所有子节点{intv=e[i];// 子节点vif(v==fa)// 跳过父节点continue;dfs_2(v,u);// 递归计算子节点的最大子树大小maxP[u]=max(maxP[u],siz[v]);// 更新最大子树大小}if(maxP[u]<=n/2)// 如果最大子树大小不超过n/2，则是重心ok[u]=true;}intmain(){cin>>n;// 输入节点数memset(h,-1,sizeof(h));// 初始化邻接表for(inti=1;i<n;i++)// 输入n-1条边{intu,v;cin>>u>>v;add(u,v),add(v,u);// 添加无向边}dfs_1(1,0);// 第一次DFS，计算子树大小dfs_2(1,0);// 第二次DFS，判断重心for(inti=1;i<=n;i++)// 遍历所有节点if(ok[i])// 如果节点i是重心{cout<<i<<endl;// 输出重心编号flag=true;// 标记有重心}if(!flag)// 如果没有找到重心cout<<"NONE"<<endl;// 输出NONEreturn0;}

【运行结果】

10 1 2 2 3 3 4 4 5 6 7 7 8 8 9 9 10 3 8 3 8