题解 | 多叉树的直径

/**
 * struct Interval {
 *  int start;
 *  int end;
 *  Interval(int s, int e) : start(start), end(e) {}
 * };
 */
#include <climits>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *

    * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类vector 树的边
     * @param Edge_value int整型vector 边的权值
     * @return int整型
     */
     //深度优先搜索，返回最大距离和远点end
    pair<int, int> dfs(int start, int father, vector< vector<pair<int, int> >>& mp){
        pair<int, int> res = {0, start};   //初始化，没有考虑下一个节点时，距离，目的节点

        for(auto elem:mp[start]){   //遍历下一个节点
            if(elem.first == father){
                continue; //跳过父节点
            }

            auto temp = dfs(elem.first, start, mp);     //和Djstra算法是一样的
            int distance = temp.first + elem.second;    //从start到经过下一个节点的最远距离
            if(distance > res.first){   
                res = make_pair(distance, temp.second);
            }
        }

        return res;
    }

    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        vector< vector<pair<int, int> >> mp(n, vector<pair<int, int>>(0));  //下标是开始节点，里面的pair是目的节点以及其距离
        int index = 0;
        for (auto struc : Tree_edge) {
            mp[struc.start].push_back( make_pair(struc.end, Edge_value[index]) ); //构造邻接表，以及其距离
            mp[struc.end].push_back( make_pair(struc.start, Edge_value[index]));  //树的边是无向的两边都连通，在邻接表中记录的是节点到下一个，有向的，则需要记录双向
            index++;
        }

        //深度优先搜索，返回最大距离和远点end
        auto one = dfs(Tree_edge.front().start, INT_MIN, mp);   //一次搜索到一个直径的端点

        auto another_one = dfs(one.second, INT_MIN, mp);

        return another_one.first;
    }
};