图论——树(1)

树分为有根，无根两种，性质有：1.连通，2.n-1条边，3无环。
dfs和bfs遍历树。
直径：树上两点之间的最长距离。两次dfs确定。
偏心距:距路径F最远的点到F的距离。核(为点的时候称为中心)为偏心距最小的点。
重心：所有子树中最大子树最小的点。（一个树最多两个，所有点到重心距离和最小）

void bfs(){
	queue<int> q;
	q.push(1);
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=1;
		for(int i=0;i<v[u].size();++i){
			if(!vis[v[u][i]]){
    			dis[v[u][i]]=dis[u]+1;
				q.push(v[u][i]);
			}
		}
	}
}
void dfs(int u,int fa){
    for(int i=0;i<v[u].size();++i){
        int v=v[u][i];
        if(v==fa)  conntinue;
        dis[v]=dis[u]+1;
        dfs(v,u);
    }
} 
//求核，直径顺带求出
#include<iostream>
#include<vector>
using namespace std;
const int  maxn=500;
struct edge{
    int v,w;
};
vector<vector<edge>> g(maxn);
int dis[maxn],fa[maxn],far,ans=1e9,flag[maxn];
void dfs(int u,int f){
    fa[u]=f;
    if(dis[u]>dis[far]) far=u;
    for(int i=0;i<g[u].size();++i){
        int  v=g[u][i].v;
        if(v==f||flag[v]) continue;
        dis[v]=dis[u]+g[u][i].w;
        dfs(v,u);
    }
}
int main(){
    int n,s;
    cin>>n>>s;
    for(int i=1;i<=n-1;++i){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    int a,b;
    dis[1]=0,dfs(1,0),a=far;
    dis[far]=0,dfs(far,0),b=far;
    for(int i=b,j=b;i;i=fa[i]){
        while(dis[j]-dis[i]>s){
            j=fa[j];
        }
        int x=max(dis[b]-dis[j],dis[i]);
        ans=min(ans,x);
    }
    for(int i=b;i;i=fa[i]){
		flag[i]=1;
	}
    for(int i=b;i;i=fa[i]){
        dis[i]=0;
        dfs(i,fa[i]);
    }
    for(int i=1;i<=n;i++){
        ans=max(ans,dis[i]);
    }
    cout<<ans;
}
//重心
void dfs(int u,int fa){
    size[u]=1;f[u]=0;
    for(int i=0;i<g[u].size();++i){
        int v=g[u][i];
        if(v==fa)  continue;
        dfs(v,u);
        size[u]+=size[v];
        f[u]=max(f[u],size[v]);
    }
    f[u]=max(f[u],n-size[u]);
    if((f[u]<f[c])||((f[u]==f[c])&&u<c)){
        c=u;
    }
}