首页 > 代码库 > 关于树的一点学习【清北学堂】
关于树的一点学习【清北学堂】
我主要在这里讲的是树的直径求法和树的重心求法
树的直径,指的就是树上距离最远两点间的一条路径。
求树的直径的方法是,首先我任选一个点,找到与它距离最远的点,记为s
再以s为起点找离他最远的点,记为v
s到v的路径即为树的直径
树的重心指的就是树上一个节点,把这个节点挖掉之后,剩下很多联通块 而重心就让这些联通块中最大的那个最小
树的重心有两种求法
一种是枚举每一个点 看把他挖掉之后会发生什么
第二种是DFS求出每个节点联通块大小
可能有人说每个节点不都连着整个树么
所以说这个联通块是算上节点自己但不算已经访问过的父节点的
好吧 问题就是找到联通块大小有什么用呢?
我们知道由于DFS 肯定每个节点都被找过
而对于每个节点来说 ,它可以把整棵树分成两部分 :我们刚刚求出来的联通块和它父亲那一块。联通块的大小我们已经求出来了,而另一半就是用n减去联通块大小
从这俩里面选一个最大的
把所有最大的聚合起来选一个最小的
完了
放代码
#include<iostream> #include<cstdio> #include<cstdlib> using namespace std; int n; int size[100000]; bool vis[100000]; struct Edge{ int next,to; }edge[100000]; int head[10000],num; inline void add(int from,int to){ edge[++num]=(Edge){head[from],to}; head[from]=num; } int ans=0x7fffffff; void dfs(int x){ vis[x]=1; for(int i=head[x];i;i=edge[i].next){ int to=edge[i].to; if(!vis[to]){ dfs(to); size[x]+=size[to]; } } int ss=n-size[x]; ans=min(ans,max(ss,size[x]-1)); } int main(){ cin>>n; int from,to; for(int i=1;i<=n;++i) size[i]=1; for(int i=1;i<n;++i){ cin>>from>>to; add(from,to); add(to,from); } dfs(1); cout<<ans<<endl; return 0; }
关于树的一点学习【清北学堂】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。