树的直径三种求法

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define ll long long
#define rint register int
#define mp(x,y) make_pair(x,y)
using namespace std;
template<typename xxx>void read(xxx &x)
{
    x=0;int f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x*=f;
}
template<typename xxx>void print(xxx x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int maxn=200020;
const int inf=0x7fffffff;
struct edge{
    int last,val,to;
}e[maxn];
int head[maxn],tot;
inline void add(int from,int to,int val)
{
    tot++;
    e[tot].to=to;
    e[tot].val=val;
    e[tot].last=head[from];
    head[from]=tot;
}
int vis[maxn];//整棵树的直径就是max{f[x]}(1 <= x <= n)
int d[maxn];//表示从节点x出发走向以x为根的子树，能够到达的最远节点的距离,d[x] = max{d[yi] + edge(x, yi)}(1 <= i <= t)
//int f[maxn];//经过节点x的最长链的长度"f[x]，f[x] = max{d[yi] + d[yj] + edge(x, yi) + edge(x, yj)}(1 <= j < i <= t),可被ans代替 
int ans,n,m;
inline void dp(int x)
{
    vis[x]=1;
    for(rint i=head[x];i;i=e[i].last)
    {
        if(vis[e[i].to]) continue;
        dp(e[i].to);
        ans=max(ans,d[x]+d[e[i].to]+e[i].val);
        d[x]=max(d[x],d[e[i].to]+e[i].val); 
    }
}
int main()
{
    read(n);read(m);
    for(rint i=1;i<=m;i++)
    {
        int a,b,c;char s[2];
        read(a);read(b);read(c);scanf("%s",s);
        add(a,b,c);add(b,a,c);
    }
    dp(1);
    print(ans);
}
/*
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define ll long long
#define rint register int
#define mp(x,y) make_pair(x,y)
using namespace std;
template<typename xxx>void read(xxx &x)
{
    x=0;int f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    x*=f;
}
template<typename xxx>void print(xxx x)
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
const int maxn=200020;
const int inf=0x7fffffff;
struct edge{
    int last,val,to;
}e[maxn];
int head[maxn],tot;
inline void add(int from,int to,int val)
{
    tot++;
    e[tot].to=to;
    e[tot].val=val;
    e[tot].last=head[from];
    head[from]=tot;
}
int vis[maxn];
int d[maxn],tmp,max_num;
int ans,n,m;
queue<int>q;
inline void bfs(int x)
{
    ans=0;
    memset(vis,0,sizeof(vis));
    memset(d,0,sizeof(d));
    vis[x]=1;q.push(x);
    while(q.size())
    {
        int x=q.front();q.pop();
        for(rint i=head[x];i;i=e[i].last)
        {
            if(!vis[e[i].to])
            {
                vis[e[i].to]=1;
                d[e[i].to]=d[x]+e[i].val;
                if(ans<d[e[i].to]) 
                {
                    ans=d[e[i].to];
                    tmp=e[i].to;
                }
                q.push(e[i].to);
            }
        }
    }
}  
inline void dfs(int x,int len)
{
    vis[x]=1;
    if(len>ans) ans=len,tmp=x;
    for(rint i=head[x];i;i=e[i].last)
        if(!vis[e[i].to]) dfs(e[i].to,len+e[i].val);
} 
int main()
{
    read(n);read(m);
    for(rint i=1;i<=m;i++)
    {
        int a,b,c;char s[2];
        read(a);read(b);read(c);scanf("%s",s);
        add(a,b,c);add(b,a,c);
    }
    dfs(1,0);
    max_num=tmp;
    memset(vis,0,sizeof(vis));
    dfs(max_num,0);
    print(ans);
}
//两遍bfs或dfs 
*/