思路：
1985也可以用1986的程序改改就行了。
但是覺得不用什么算法也是可以做出1985的。
想了一下，發(fā)現(xiàn)：
路徑的最大值一定存在于兩個葉子節(jié)點(diǎn)中。
如果只有一個葉子，那整個樹就是一條直線了。
由于我們只是考慮葉子節(jié)點(diǎn)。那么對于每一個非葉子節(jié)點(diǎn)，我們只需要找出它下面的所有節(jié)點(diǎn)中，離它最遠(yuǎn)的兩個葉子就行了。
這兩個葉子節(jié)點(diǎn)的距離也就有可能成為答案。
對于每個點(diǎn)，我們只需要保存一個值，就是該點(diǎn)下面的所有節(jié)點(diǎn)中，距離它最遠(yuǎn)的一個葉子節(jié)點(diǎn)，和它的距離。
對于每個點(diǎn)，遍歷完它的孩子之后，就知道“離它最遠(yuǎn)的兩個葉子的距離”了。
注意：
代碼里需要處理“一條直線連著幾個點(diǎn)”這種情況，將這樣的幾個點(diǎn)縮成一個點(diǎn)比較好。不做這個處理一定會爆棧。最后一個數(shù)據(jù)是一條直線。（陰險）
這份代碼跑了141MS，還算可以，呵呵。應(yīng)該比直接用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;
}