思路：

题目的主要信息：

• 要求树的直径，即树上两点最远距离
• 这里的树不止是二叉树，都有可能
• 题目给的Tree_edge是一个点到另一个点有边，Edge_value为与之对应的边的权重weigh

方法一：两次深度优先搜索

首先我们要知道一个性质：从树的根节点深度优先搜索到最远距离，再从最远距离深度优先搜索到另一最远距离就是树的直径。

具体做法：

我们需要用map即哈希表来存储树的边结构，将树看成图，以权重构建无向图，存入map中。这里便是遍历Tree_edge和Edge_value，将它们的信息存入map中。 再从顶点出发，利用dfs找到最远距离，第二次以当前最远距离再次调用dfs找到最远距离，第二个最远距离即是树的直径。

class Solution {
public:
    struct edge{ //构建边的结构
        int end;
        int weigh;
        edge(int _end, int _weigh): end(_end), weigh(_weigh){}
    };
    //深度优先函数
    void dfs(map<int, vector<edge>>& graph, vector<int>& res, int start, int pre, int length){
        vector<edge> edges = graph[start];
        for(int i = 0; i < edges.size(); i++){ //遍历与这个点相连的每一条边
            if(edges[i].end != pre){
                length += edges[i].weigh;
                if(length > res[0]){
                    res[0] = length;
                    res[1] = edges[i].end;
                }
                dfs(graph, res, edges[i].end, start, length);
                length = length - edges[i].weigh; //回溯
            }
        }
    }
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        if(Tree_edge.size() == 0 || Edge_value.size() == 0)
            return 0;
        if(Tree_edge.size() != Edge_value.size())
            return 0;
        map<int, vector<edge> > graph; //用map构建图，key为顶点编号，vector中记录与之相连的边
        for(int i = 0; i < Tree_edge.size(); i++){ //遍历边的集合
            Interval temp = Tree_edge[i];
            int weigh = Edge_value[i];
            edge e1 = edge(temp.end, weigh); //在图中将start与end相连
            if(!graph.count(temp.start)){
                vector<edge> v;
                graph[temp.start] = v;
            }
            graph[temp.start].push_back(e1);
            edge e2 =edge(temp.start, weigh);
            if(!graph.count(temp.end)){
                vector<edge> v;
                graph[temp.end] = v;
            }
            graph[temp.end].push_back(e2);    
        }
        vector<int> length(2, 0);  //第一个零表示以第0个结点为起点的最长路径长度，第二个零表示最长路径的重点序列
        dfs(graph, length, 0, -1, 0);   //从0结点深度优先找最远距离
        vector<int> res(2, 0); 
        dfs(graph, res, length[1], -1, 0); //以刚刚找到的最远距离再次深度优先找最元距离即是答案
        return res[0];
    }
};

复杂度分析：

• 时间复杂度：O(n)，因为是哈希表存储可以直接访问
• 空间复杂度：O(n)，递归栈最大深度

方法二：两次广度优先搜索

具体做法：

同理，有dfs就会有bfs，同样是两次bfs即可得到树的直径。树的bfs属于层次遍历，于是需要使用队列将子结点压入队列中，后续再依次访问。

class Solution {
public:
    int dis[200020];  //记录路径长度
    bool vist[100020]; //访问过的记录，防止重复
    vector<pair<int, int> > v[100020];  //树两个结点之间的边
    int ans = 0;
    int bfs(int x) //广度优先函数
    {
        memset(vist, 0, sizeof(vist));
        memset(dis, 0, sizeof(dis));
        vist[x] = 1;
        queue<int> q;  //bfs依赖队列，层次遍历
        q.push(x);
        int point = 0;
        int cur_point = x;  //表示当前结点,后面会更新
        while(!q.empty())
        {

            cur_point = q.front();
            q.pop();
            if(dis[cur_point] >= ans) //找最远距离
            {
                ans = dis[cur_point]; 
                point = cur_point; 
            }
            pair<int,int> temp;
            for(int i = 0; i < v[cur_point].size(); i++)
            {
                temp = v[cur_point][i];
                if(!vist[temp.first])   //之前没有访问过的点才进入下面
                {
                    vist[temp.first] = true;  //标记访问过的结点
                    dis[temp.first] = temp.second + dis[cur_point];  //相邻点加上当前这条边
                    q.push(temp.first);
                }
            }
        }
        return point;
    }
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        if(Tree_edge.size() == 0 || Edge_value.size() == 0)
            return 0;
        if(Tree_edge.size() != Edge_value.size())
            return 0;
        for(int i = 0; i < Tree_edge.size(); i++){ //将给的边相连加入v中
            v[Tree_edge[i].start].push_back(make_pair(Tree_edge[i].end, Edge_value[i]));
            v[Tree_edge[i].end].push_back(make_pair(Tree_edge[i].start, Edge_value[i]));
        }
        int point = bfs(1); //两次bfs
        point = bfs(point);
        return ans;
    }
};

复杂度分析：

• 时间复杂度：O(n^2)，因为使用了邻接矩阵，相当于遍历矩阵
• 空间复杂度：O(n^2)，邻接矩阵的空间及其他辅助数组