D54 树的直径 三次DFS P4408 [NOI2003] 逃学的小孩

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
struct edge{int x,y,c,pre;}a[N*2];int alen,last[N];
void ins(int x,int y,int c){alen++;a[alen]=edge{x,y,c,last[x]};last[x]=alen;}
long long rad,d[N];
void dfs1(int x,int fa,int &p)
{
    for(int k=last[x];k;k=a[k].pre) 
	{
        int y=a[k].y;if(y==fa)continue;
        d[y]=d[x]+a[k].c;
        if(d[y]>rad)rad=d[y],p=y;
        dfs1(y,x,p);
    }
}
void dfs2(int x,int fa) 
{
    for(int k=last[x];k;k=a[k].pre) 
	{
        int y=a[k].y;if(y==fa)continue;
        d[y]=min(d[y],d[x]+a[k].c);
        dfs2(y,x);
    }
}
int main() 
{
	int n,m;scanf("%d%d",&n,&m);
	alen=0;memset(last,0,sizeof(last));
    for(int i=1,x,y,c;i<=m;i++)
	{
        scanf("%d%d%d",&x,&y,&c);
        ins(x,y,c);
        ins(y,x,c);
    }
    int L,R;
    d[1]=rad=0;dfs1(1,0,L);
    d[L]=rad=0;dfs1(L,0,R);
    long long ans=rad;
    memset(d,0x3f,sizeof(d));//d[i]表示到L或R最近距离
    d[L]=0;dfs2(L,0);
    d[R]=0;dfs2(R,0);
    long long res=0;for(int i=1;i<=n;i++) res=max(res,d[i]);
    printf("%lld",ans+res);
    return 0;
}