题意理解

n个房子对应于n个结点，街道就对应于结点之间的边，构成一张连通图。找到这张图中哪两点之间边上的数值之和最大。

方法一

深度优先搜索
使用二维数组path存储路径的信息，对于每一个点，要记录它和其它结点所有路径的长度。然后以每一个点分别作为起点，都进行一次深度优先搜索，每走一步都更新一次最长路径ans，注意这里的ans不需要退回。

示意图如下，最终答案对应的路径是1-5-2-3这一条路径的长度：

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最终结果
     * @param n int整型 城市数量
     * @param u int整型vector 
     * @param v int整型vector 
     * @param w int整型vector 
     * @return long长整型
     */
    vector<pair<int, int>> path[100000];
    long long ans=0;
    //x表示这一步的起点，pre表示上一步的起点
    void dfs(int x, int pre, long long sum) {
        for (int i=0;i<path[x].size();i++) {
            //不能往回走
            if (path[x][i].first==pre) continue;
            //不断更新ans
            ans = max(sum + path[x][i].second, ans);
            dfs(path[x][i].first, x, sum+path[x][i].second);
        }
    }


    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        //path每个位置记录该点与其它点存在的连边
        for (int i=0;i<n-1;i++) {
            path[u[i]].push_back({v[i],w[i]});
            path[v[i]].push_back({u[i],w[i]});
        }
        //对每个结点作为起始点进行dfs
        for (int i=1;i<=n;i++) {
            if (path[i].size()==1) {
                dfs(i,i,0);
            }
        }
        return ans;
    }
};

时间复杂度：。每一个点作为起点遍历了一遍整个点集，是的时间，n个点总共是。
空间复杂度：。创建了一个二维数组来存储路径和点的信息。

方法二

对于一条路径，我们可以把它看成两条路径在同一结点处的拼接，以该点为连接点。所以，我们在递归的时候，不断更新维护每一个点的某两个子树child_i,child_j中最长路径相加得到的最大值。
同时，我们不需要考虑来时路径所在的子树child_v，因为如果以结点u为拼接点的最长路径来自于child_v和某个child_i，则这种情况会在以v为拼接点时考虑进去。

最重要的一点，在每一层的中，我们遍历当前拼接点x的path[x]之后，就已经完成了对x点所以情况的搜索，这与方法一是不一样的，方法一只是完成了以某个特定点为起点，经过x的路径的搜索。这导致我们在主程序中不需要循环调用dfs。

例如在方法一的图中，以5为例，它有4子树，以5为拼接点的最长路径可能是其中某两个子树的拼接。

具体代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最终结果
     * @param n int整型 城市数量
     * @param u int整型vector 
     * @param v int整型vector 
     * @param w int整型vector 
     * @return long长整型
     */
    vector<pair<int, int>> path[100000];
    long long ans=0;
    //x表示这一步的起点，pre表示上一步的起点
    long long dfs(int x, int pre){
        long long child1 = 0;
        for(int i=0;i<path[x].size();i++){
            if(path[x][i].first != pre){
                long long child2 = dfs(path[x][i].first, x) + path[x][i].second;
                //更新ans
                ans = max(ans, child1+child2);
                //保留更长的子树中的路径
                child1 = max(child1, child2);
            }
        }
        return child1;
    }

    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        //path每个位置记录该点与其它点存在的连边
        for (int i=0;i<n-1;i++) {
            path[u[i]].push_back({v[i],w[i]});
            path[v[i]].push_back({u[i],w[i]});
        }
        //选择任意一个点开始
        dfs(1, 0);
        return ans;
    }
};

时间复杂度：。仅仅在递归过程中遍历了一遍所有的点，主程序中没有对dfs进行循环调用。
空间复杂度：。和方法一一样，创建了一个二维数组来存储路径和点的信息。