C++简洁代码 | #树的直径#

证明过程：https://www.icode9.com/content-4-734332.html

class Solution {
private:
    vector<vector<pair<int, int>>> graph;
    int max_dist = 0, max_idx = 0;
public:
    // 两次DFS，需要看证明过程
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        // write code here
        // 建立图，采用邻接表的格式
        graph.resize(n);
        int e_n = Tree_edge.size();
        for (int i = 0; i < e_n; ++i) {
            int node1 = Tree_edge[i].start;
            int node2 = Tree_edge[i].end;
            graph[node1].emplace_back(node2, Edge_value[i]);
            graph[node2].emplace_back(node1, Edge_value[i]);
        }
        // 第一次从任意节点开始，找距离最远的节点A
        dfs(0, -1, 0);
        // 第二次从A出发，寻找距离最远的节点
        dfs(max_idx, -1, 0);
        return max_dist;
    }

    void dfs(int cur, int parent, int dist) {
        for (auto& e : graph[cur]) {
            if (e.first != parent) {
                dfs(e.first, cur, dist + e.second);
            }
        }
        if (dist > max_dist) {
            max_dist = dist;
            max_idx = cur;
        }
    }
};