思路：
1985也可以用1986的程序改改就行了。
但是觉得不用什么算法也是可以做出1985的。
想了一下，发现：
路径的最大值一定存在于两个叶子节点中。
如果只有一个叶子，那整个树就是一条直线了。
由于我们只是考虑叶子节点。那么对于每一个非叶子节点，我们只需要找出它下面的所有节点中，离它最远的两个叶子就行了。
这两个叶子节点的距离也就有可能成为答案。
对于每个点，我们只需要保存一个值，就是该点下面的所有节点中，距离它最远的一个叶子节点，和它的距离。
对于每个点，遍历完它的孩子之后，就知道“离它最远的两个叶子的距离”了。
注意：
代码里需要处理“一条直线连着几个点”这种情况，将这样的几个点缩成一个点比较好。不做这个处理一定会爆栈。最后一个数据是一条直线。（阴险）
这份代码跑了141MS，还算可以，呵呵。应该比直接用lca要快。
#include <stdio.h>
#define MAX_N 40032
struct edge_node 
{
struct edge_node *next;
int idx, len;
};
struct edge_node edges[MAX_N*2];
struct tree_node {
struct edge_node *edge;
int visited;
};
struct tree_node tree[MAX_N];
int max_val;
__inline void add_edge(int idx, int a, int b, int len)
{
struct edge_node *e = &edges[idx];
e->idx = b;
e->len = len;
e->next = tree[a].edge;
tree[a].edge = e;
}
int dfs(int idx)
{
struct edge_node *e;
int sum, cnt, arr[2], r;
sum = 0;
while (1) {
tree[idx].visited = 1;
cnt = 0;
for (e = tree[idx].edge; e; e = e->next)
cnt += !tree[e->idx].visited;
if (!cnt)
return sum;
if (cnt > 1)
break;
for (e = tree[idx].edge; tree[e->idx].visited; e = e->next);
sum += e->len;
idx = e->idx;
}
arr[0] = arr[1] = 0;
for (e = tree[idx].edge; e; e = e->next) {
if (tree[e->idx].visited)
continue;
r = dfs(e->idx) + e->len;
if (r >= arr[1]) {
arr[0] = arr[1];
arr[1] = r;
} else if (r >= arr[0])
arr[0] = r;
}
r = arr[0] + arr[1];
if (r > max_val)
max_val = r;
return arr[1] + sum;
}
int main()
{
int m, n, a, b, len, i;
char str[16];
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d", &n, &m);
for (i = 0; i < m*2; i += 2) {
scanf("%d%d%d%s", &a, &b, &len, str);
add_edge(i, a, b, len);
add_edge(i + 1, b, a, len);
}
for (i = 1; i <= n; i++) {
if (tree[i].visited)
continue;
a = dfs(i);
if (a > max_val)
max_val = a;
}
printf("%d\n", max_val);
return 0;
}