题解 | #多叉树的直径#

/**
 * struct Interval {
 *	int start;
 *	int end;
 *	Interval(int s, int e) : start(start), end(e) {}
 * };
 */

// 求树的直径，一次 dfs 即可，每次记录最大值、次大值，即以当前节点为中间点的最长直径，每次维护 res 即可

 const int N = 200010;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类vector 树的边
     * @param Edge_value int整型vector 边的权值
     * @return int整型
     */
    
    int e[N], ne[N], h[N], w[N], idx = 0;
    int res = 0;

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

    int dfs(int u, int fa)
    {
        int Max = 0, Maxx = 0;
        for (int i = h[u]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (j == fa) continue;
            int x = dfs(j, u) + w[i];
            if (x > Max)
            {
                Maxx = Max;
                Max = x;
            }
            else if (x >= Maxx) Maxx = x;
        }
        res = max(res, Maxx + Max);
        return Max;
    }

    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        // write code here
        memset(h, -1, sizeof h);

        for (int i = 0; i + 1 < n; i ++) 
        {
            add(Tree_edge[i].start, Tree_edge[i].end, Edge_value[i]);
            add(Tree_edge[i].end, Tree_edge[i].start, Edge_value[i]);
        }
        dfs(1, -1);
        return res;
    }
};