树。

int fa[][M],depth[];
void dfs(int fr,int x){
	fa[x][0]=fr;
	depth[x]=depth[fr]+1;
	for(int i=1;i<M;i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];
	}
	for(int i=head[x];i;i=e[i].next){
		int v=e[i].to;
		if(v!=fr && v!=x) dfs(x,v);
	}
}//预处理大跳祖先
int lca(int x,int y){
	int ans=-1,i=M-1;
	if(depth[x]<depth[y]) swap(x,y);
	while(depth[x]>depth[y]){
		if(depth[fa[x][i]]>=depth[y]) x=fa[x][i];
		//跳。 
		else i--;
	}
	if(x!=y){
		i=M-1;
		while(fa[x][0]!=fa[y][0]){
			if(fa[x][i]!=fa[y][i]){
				x=fa[x][i];
				y=fa[y][i];
				//跳。 
			}else i--;
		}
		ans=fa[x][0];
	}else ans=x;
	return ans;
}

int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
} 
void unionn(int x,int y){
	fa[find(x)]=find(y);
}
//并查集 
void Kruskal(){
	sort(e)//边权从小到大排序
	for(int i=1,k=0;i<=m && k<n-1;i++){
		if(find(e[i].u)!=find(e[i].v)){
			unionn(e[i].u,e[i].v);
			sum+=e[i].w;
			k++;//k为最小生成树目前边数 
		}
	} 
}

int minn[]={ ∞},f[],sum;
void prim(){
	minn[1]=0;//随机选点为起点
	int u=1,tmp=0;
	while(u){
		f[u]=1;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			minn[v]=min(minn[v],e[i].w);
		}
		u=0,tmp= ∞;
		for(int i=1;i<=n;i++){
			if(!f[i] && tmp>minn[i]){
				tmp=minn[i];
				u=i;
			}
		} 
		if(u) sum+=tmp;
	} 
}

int dfs(int u,int fr){
	int maxn=0,sum=0;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v!=fr){
			int tmp=dfs(v);
			maxn=max(maxn,tmp);
			sum+=tmp;
		}
	}
	maxn=max(maxn,n-sum-1);
	if(maxson<maxn){
		maxson=maxn;
		ans=u;
	}
	return sum+1;
}

void dfs(int u){
	f[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(!f[v]){
			d[v]=d[u]+e[i].w;
			if(maxn<d[v]){
				maxn=d[v];
				id=v;
			}
			dfs(v);
		}
	}
}
int main(){
	dfs(1);
	dfs(id);
	return 0;
}

void dp(int u,int fr){
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v!=fr){
			dp(v,u);
			f[u]=max(f[u],d[u]+d[v]+e[i].w);
			f[u]=max(f[u],f[v]);
			d[u]=max(d[u],d[v]+1);
		}
	}
}