学步园

解题步骤：

1. 首先用深搜，判断环路；

2 再用一次深搜，找出最大直径；

注意点：

1. 数据范围较大，用递归会爆栈，得手动开栈

#pragma comment(linker, "/STACK:102400000,102400000")

    2.每个节点只用保存两个变量：max：以该节点为根节点，的最大直径； max_len：以该节点为根节点的最长孩子深度；

最大max：if((temp = node[edge[i].node].max_len + edge[i].len + node[root].max_len) > node[root].max)

         
     node[root].max = temp;

     
最大max_len: if(temp > node[root].max_len) 

 node[root].max_len = temp;

#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXE 2000005
#define MAXN 100005
struct Edge{
    int node;
    int next;
    int len;
}edge[MAXE];
struct Node{
    int max;
    int max_len;
}node[MAXN];
int head[MAXN], cnt;
void add(int a, int b, int c)
{
    edge[cnt].node = b; edge[cnt].len = c; edge[cnt].next = head[a]; head[a] = cnt ++;
    edge[cnt].node = a; edge[cnt].len = c; edge[cnt].next = head[b]; head[b] = cnt ++;
}
bool vis[MAXN];
bool dfs(int root, int fa)
{
    vis[root] = 1;
    for(int i = head[root]; ~i; i = edge[i].next)
    {
        if(edge[i].node != fa)
        {
            if(vis[edge[i].node])
                return 0;
            if(dfs(edge[i].node, root) == 0)
                return 0;
        }
    }
    return 1;
}
int max;
int dp(int root, int fa)
{
    vis[root] = 0;
    node[root].max_len = node[root].max = 0;
    for(int i = head[root]; ~i; i = edge[i].next)
    {
        if(edge[i].node != fa)
        {
            dp(edge[i].node, root);
            int temp;
            if((temp = node[edge[i].node].max_len + edge[i].len + node[root].max_len) > node[root].max)
                node[root].max = temp;
            if(temp > node[root].max_len)
                node[root].max_len = temp;
        }
    }
    if(node[root].max > max)
        max = node[root].max;
    return 0;
}
int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        memset(head, -1, sizeof(head));
        cnt = 0;
        while(m--)
        {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        memset(vis, 0, sizeof(vis));
        int i;
        for(i = 1; i <= n; ++i)
        {
            if(!vis[i])
            {
                if(!dfs(i, -1))
                    break;
            }
        }
        if(i <= n)
            printf("YES\n");
        else
        {
            for(int i = 1; i <= n; ++i)
            {
                if(vis[i])    dp(i, -1);
            }
            printf("%d\n", max);
        }
    }
    return 0;
}