题解 | 多叉树的直径

/**
 * struct Interval {
 *  int start;
 *  int end;
 *  Interval(int s, int e) : start(start), end(e) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类vector 树的边
     * @param Edge_value int整型vector 边的权值
     * @return int整型
     */
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        // write code here
        if (n <= 1) return 0;
        vector<vector<pair<int, int>>> g(n);
        for (int i = 0; i < Tree_edge.size(); ++i) {
            int u = Tree_edge[i].start, v = Tree_edge[i].end, w = Edge_value[i];
            g[u].push_back({v, w});
            g[v].push_back({u, w});
        }

        auto far = [&](int s) {
            vector<long long> d(n, -1);
            queue<int> q;
            q.push(s);
            d[s] = 0;
            int u = s;
            while (!q.empty()) {
                u = q.front();
                q.pop();
                for (auto& e : g[u]) if (d[e.first] == -1) {
                        d[e.first] = d[u] + e.second;
                        q.push(e.first);
                    }
            }
            int id = s;
            long long mx = 0;
            for (int i = 0; i < n; ++i) if (d[i] > mx) mx = d[i], id = i;
            return pair<int, long long>(id, mx);
        };

        auto a = far(0);          // 任选一点
        auto b = far(a.first);    // 到最远点的最远距离即直径
        return b.second;
    }
};