$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题是一个固定的模板，求由无向图组成的树中的直径（路径最长的路径，权值允许出现负数）

我们从集合的角度来考虑就是，当前有一堆路径，我们需要找出这些路径当中路径和最大的路径

反过来推就是，我们需要一种方式来表示这些路径

如果我们通过枚举两个端点的话，时间复杂度为 $O(n^2)$ ，显然会超时，我们需要换一种表述路径的方法

如果我们用某个点来表示所有经过该点的路径，那么这个点可以表示很多路径（废话），我们取这些路径当中路径和最大的即可

具体地，对于某个点 $u$ 而言，经过它的路径有三种情况：

• 该路径的其中一个端点在 $u$ 的一棵子树中，另一个端点为 $u$

直接递归各个子树取最大值即可

• 该路径的两个端点在 $u$ 的两个不同子树中

我们递归所有子树，取出最大值和次大值然后相加即可

具体地，我们用 $d1,\ d2$ 表示最大值和次大值，用 $d$ 表示当前计算得出的值，有

    if(d >= d1) d2 = d1, d1 = d;
    else if(d >= d2) d2 = d;

• 该路径的一个端点在 $u$ 的子树中，另一个在 $u$ 的上方

这种情况不合法，需要排除

完整代码：

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e4 + 10, M = 2 * N;

int h[N], e[M], w[M], ne[M], idx;
int n;
int ans;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u, int father)//由于树是无向图，需要保证不往回走
{
    int dist = 0;//当前节点往下的最长路径
    int d1 = 0, d2 = 0;//表示最大值和次大值，0可以忽略
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];//得到子树的根节点
        if(j == father) continue;//一旦往回走就跳过
        int d = dfs(j, u) + w[i];

        dist = max(dist, d);

        if(d >= d1) d2 = d1, d1 = d;
        else if(d >= d2) d2 = d;
    }
    ans = max(ans, d1 + d2);//包含当前节点在内的最长路径
    return dist;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for(int i = 1; i <= n - 1; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    dfs(1, -1);

    cout << ans << endl;

    return 0;
}