首页 > 代码库 > 关于树的一点学习【清北学堂】

关于树的一点学习【清北学堂】

2024-10-28 22:01:39   211人阅读

　　我主要在这里讲的是树的直径求法和树的重心求法

　　树的直径，指的就是树上距离最远两点间的一条路径。

　　求树的直径的方法是，首先我任选一个点，找到与它距离最远的点，记为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;
}

 

关于树的一点学习【清北学堂】


联系
我们