树的直径

树的直径：

利用了树的直径的一个性质：距某个点最远的叶子节点一定是树的某一条直径的端点。

先从任意一顶点a出发，bfs找到离它最远的一个叶子顶点b,然后再从b出发bfs找到离b最远的顶点c,那么b和c之间的距离就是树的直径。

用dfs也可以。

http://poj.org/problem?id=1985

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
inline int read(){
	int sum=0,x=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			x=0;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		sum=(sum<<1)+(sum<<3)+(ch^48),ch=getchar();
	return x?sum:-sum;
}
inline void write(int x){
	if(x<0)
		putchar('-'),x=-x;
	if(x>9)
		write(x/10);
	putchar(x%10+'0');
}
const int M=4e4+4;
struct node{
	int v,w,nextt;
}e[M<<1];
int head[M],book[M],dis[M],n,flag,maxx,tot,b;
void bfs(int s){
	if(!flag)
		flag=1;
	else{
		for(int i=0;i<=n;i++)
			book[i]=0,dis[i]=0;
	}
	book[s]=1;
	queue<int>que;
	que.push(s);
	b=s;
	maxx=0;
	while(!que.empty()){
		int u=que.front();
		que.pop();
		for(int i=head[u];~i;i=e[i].nextt){
			int v=e[i].v;
			if(!book[v]){
				book[v]=1;
				que.push(v);
				dis[v]=dis[u]+e[i].w;
				if(dis[v]>maxx){
					maxx=dis[v];
					b=v;
				}
			}
		}
	}
}
void addedge(int u,int v,int w){
	e[tot].v=v;
	e[tot].w=w;
	e[tot].nextt=head[u];
	head[u]=tot++;
}
char s[2];
int main(){
	int m;
	n=read(),m=read();
	for(int i=0;i<=n;i++)
		head[i]=-1;
	while(m--){
		int u=read(),v=read(),w=read();
		scanf("%s",s);
		addedge(u,v,w);
		addedge(v,u,w);
	}
	bfs(1);
	bfs(b);
	write(maxx);
	putchar('
');
	return 0;
}

再来一道：https://cometoj.com/problem/1361?redirect=%2Fproblem%2F1361

题意：给一颗树，树边权为1，选定k个点作为点集S，S中的点俩俩可达且不需要经过除了S以外的点，让其他点到集合S的最大距离最小化，求最小可能的最大距离

分析：我们考虑俩个点u，v。当dis[u，v]达到最大值时，是不是我们就要选取u，v之间简单路径的中点作为点集S的其中一点　　　才是最优的？答案肯定是这样的，又由于属于集合S的点俩俩必须不经过其他点，所以其他店必然是从这个中点扩展出去　　　的，这个扩展我们用堆来实现，预处理完从这个中心点到叶子节点的距离，每次都删除去最大距离然后把与删去节点相　　　邻的边加到堆里面，执行k次后就能得到答案。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int b,maxx,n,k;
const int M=1e5+5;
int dis[M],vis[M],pre[M],len[M],path[M];
vector<int>g[M];
void bfs(int s){
    queue<int>que;
    maxx=0;
    memset(pre,-1,sizeof(pre));
    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));
    dis[s]=1;
    que.push(s);
    vis[s]=1;
    while(!que.empty()){
        int u=que.front();
        que.pop();
        for(auto v:g[u]){
            if(!vis[v]){
                dis[v]=dis[u]+1;
                pre[v]=u;
                vis[v]=1;
                que.push(v);
                if(maxx<dis[v]){
                    maxx=dis[v];
                    b=v;
                }
            }
        }
    }
}
void dfs(int u){
    vis[u]=1;

    for(auto v:g[u]){
        if(!vis[v]){
            dfs(v);
            len[u]=max(len[u],len[v]+1);
        }
    }
}
struct node{
    int u,w;
    bool operator<(const node &b)const{
        return w<b.w;
    }
};
void solve(int s){
    priority_queue<node>que;
    que.push(node{s,len[s]});
    vis[s]=1;
    while(k){
        node u=que.top();
        que.pop();
        for(auto v:g[u.u]){
            if(!vis[v]){
                que.push(node{v,len[v]});
                vis[v]=1;
            }
        }
        k--;
    }
   /// cout<<que.top().u<<"~~~~"<<endl;
    printf("%d
",que.top().w+1);
}
int main(){

    scanf("%d%d",&n,&k);
    for(int u,v,i=1;i<n;i++){
        scanf("%d%d",&u,&v);
        g[u].pb(v);
        g[v].pb(u);
    }
    ///相当于找直径
    bfs(1);
    int sta=b;
    bfs(b);
    int ed=b;
    int tot=0;
    while(ed!=-1)
        path[tot++]=ed,ed=pre[ed];

    int midd=path[tot/2];
    memset(vis,0,sizeof(vis));
    dfs(midd);
    memset(vis,0,sizeof(vis));
    solve(midd);
    return 0;
}