lca和树的直径wa3 4

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<cmath>
#include<map>

const int maxn=2e5+5;

using namespace std;
int read() {
	int sum=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return f*sum;
}
long long llread() {
	long long sum=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return f*sum;
}
int n,m,k,t,mid;
int hd[maxn],fa[maxn][30],node1,node2;
long long dep[maxn];
long long maxdep,ans;
bool cmp(int a,int b){
	return a>b;
}
struct edge{
	int u,v,nxt;
	long long w;
}e[maxn*2];
void addedge(int u,int v,long long w){
	e[++t].u=u,e[t].v=v,e[t].nxt=hd[u],e[t].w=w,hd[u]=t;
}
void dfs1(int u,int fath){
	if(dep[u]>maxdep){
		maxdep=dep[u];
		node1=u;
	}	
	for(int i=hd[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fath)continue;
		dep[v]=dep[u]+e[i].w;
		dfs1(v,u);
	}
}
void dfs2(int u,int fath){
	fa[u][0]=fath;
	if(dep[u]>maxdep){
		maxdep=dep[u];
		node2=u;
	}	
	for(int i=hd[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fath)continue;
		dep[v]=dep[u]+e[i].w;
		dfs2(v,u);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y])
		swap(x,y);
	for(int j=25;j>=0;j--)
		if(dep[fa[x][j]]>=dep[y])
			x=fa[x][j];
	if(x==y)return x;
	for(int j=25;j>=0;j--)
		if(fa[x][j]!=fa[y][j])
			x=fa[x][j],y=fa[y][j];
	return fa[x][0];
}
long long getdis(int x,int y){
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int main(){
	freopen("P4408_3.in","r",stdin);
	n=read(),m=read();
	for(int i=1,u,v;i<=m;i++){
		long long w;
		u=read(),v=read(),w=llread();
		addedge(u,v,w);
		addedge(v,u,w);
	}
	dfs1(1,1);
	memset(dep,0,sizeof(dep));maxdep=0;
	dfs2(node1,node1);
	for(int j=1;j<=25;j++)
		for(int i=1;i<=n;i++)
			fa[i][j]=fa[fa[i][j-1]][j-1];
	for(int i=1;i<=n;i++)
		if(i==node1||i==node2)continue;
		else ans=max(ans,min(getdis(i,node1),getdis(i,node2))+maxdep);
	printf("%lld",ans);
	return 0;
}