树的直径

树的直径求法：

1. 任取一点u，找到树上距u最远的点s
2. 找到树上距s点最远的点t，s->t的距离即为所求

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <queue>

using namespace std;

int init(){

	int rv=0,fh=1;

	char c=getchar();

	while(c<'0'||c>'9'){

		if(c=='-') fh=-1;

		c=getchar();

	}

	while(c>='0'&&c<='9'){

		rv=(rv<<1)+(rv<<3)+c-'0';

		c=getchar();

	}

	return fh*rv;

}

const int MAXN=30005;

int n,m,head[MAXN],nume,q,dis[MAXN];

struct edge{

	int to,nxt,dis;

}e[MAXN<<1];

void adde(int from,int to,int dis){

	e[++nume].to=to;

	e[nume].nxt=head[from];

	head[from]=nume;

	e[nume].dis=dis;

}

bool f[MAXN];

int bfs(int s){

	queue<int>q;

	q.push(s);

	dis[s]=0;

	memset(dis,0,sizeof(dis));

	memset(f,0,sizeof(f));

	f[s]=1;

	while(!q.empty()){

		int u=q.front();q.pop();

		for(int i=head[u];i;i=e[i].nxt){

			int v=e[i].to;

			if(!f[v]){

				q.push(v);

				f[v]=1;

				dis[v]=dis[u]+e[i].dis;

			}

		}

	}

}

int main(){

	freopen("in.txt","r",stdin);

	int u,v,di;

	while(~scanf("%d%d%d",&u,&v,&di)){

		n=max(n,u);n=max(n,v);

		adde(u,v,di);adde(v,u,di);

	}

	bfs(1);

	int t=0,ma=0;

	for(int i=1;i<=n;i++){

		if(ma<dis[i]){

			ma=dis[i];

			t=i;

		}

	}

	//cout<<t<<endl;

	bfs(t);

	ma=0;

	//for(int i=1;i<=n;i++) cout<<dis[i]<<endl;

	for(int i=1;i<=n;i++){

		if(ma<dis[i]){

			ma=dis[i];

		}

	}

	cout<<ma;

	fclose(stdin);

	return 0;

}