制作网站注册页面,wordpress vip 插件下载,wordpress扫码支付,个人主页写什么内容题目一#xff1a;树的重心
846. 树的重心 - AcWing题库 分析
采用暴力枚举#xff0c;试探每个点#xff0c;除去之后#xff0c;连通分量最大值是多少#xff0c; 各个点的最大值找最小的
因为可以通过 dfs 来得到 根u以下点数#xff0c;以及可以求各分树的点数树的重心
846. 树的重心 - AcWing题库 分析
采用暴力枚举试探每个点除去之后连通分量最大值是多少 各个点的最大值找最小的
因为可以通过 dfs 来得到 根u以下点数以及可以求各分树的点数
所以采用 邻接表存储数据的方式。
vis 标记搜索
需要存 最终答案 ans
需要存每个顶点及其以下点数 sum 需要存每个顶点子树 res
代码
#includebits/stdc.h
using namespace std;const int N 1e510, M 2*N;int h[N], e[M], ne[M], idx;
int n;
int ans N; bool vis[N];
// 前插法将b插入a链表
void add(int a, int b) {e[idx] b, ne[idx] h[a], h[a] idx;
}
// 以u为根子树的点的大小
int dfs(int u) {vis[u] true; // 搜索int sum 1, res 0; // 以u为根子树大小 ans 为除去根for(int i h[u]; i ! -1; i ne[i]) {int j e[i];if(!vis[j]) {int s dfs(j);res max(res,s); // 该根多个子树的最大值sum s; // 该根往下的总和}}res max(res,n-sum); // 该根往下最大值以及 剩下的比较ans min(ans,res); //求到了除去u连通分量点最大值 更新暴力枚举中每个u的最小值。return sum;//往上返回点数
}int main() {memset(h,-1,sizeof h);cin n;for(int i 0; i n-1; i ) {int a, b;cin a b;add(a,b), add(b,a); // 搭建无向图}dfs(1);//都是可以相通的随便dfs一个顶点cout ans endl;return 0;
}
