描述

城市 AA 新建了 nn 个座房子，城市规划处用 n-1n−1 条双向街道将房子连在一起，使得任意两座房子之间有且仅有一条道路可达。牛牛和牛妹将被随机分到两个房子，现在牛牛想知道，他和牛妹房子的最长路径是多少。

示例1

输入： 
7,[2,3,5,4,5,5],[5,2,1,6,7,4],[15,6,14,4,1,6]
复制
返回值： 
35
复制
说明： 
当牛牛和牛妹分别被分到 11 , 33 两个房子时，路径最长。

备注： 

		
		

			房子 uu , 房子 vv , 街道长度 ww。
		


		

			表示房子 u_iui 与房子 v_ivi 之间有一条长度为 w_iwi的道路相连。
		


		

			(1 \leq u, v \leq n, u \neq v, 1 \leq w \leq 100,000)(1≤u,v≤n,u=v,1≤w≤100,000) 。
解题思路：
1）本题为图的遍历，先构图。注意此时用到vector+pair的数据结构，即构建一个整数对数组，注意初始化的时候一定要给数组长度初始化，这样之后使用push_back即为给整数对赋值； 
vector<pair<int, int>>num[100001];
2）要找最长路径，不难看出最长路径的两个端点有且仅有一个邻居节点；
3）找出仅有一个邻居节点的端点，进行dfs深度优先搜索；
4）dfs的参数分别为当前到达的节点a，上一个搜索的节点b，以及当前路径和sum。
为什么要传节点b呢，这是为了防止重复计算，比如5的邻居几点是2，在5节点遍历2后如果不做记录，那在2节点遍历邻居节点时肯定会遍历到5，这样会造成重复计算甚至是原路返回。
另外要特别注意sum参数，在做dfs嵌套调用时千万不能把sum+w重新赋值给sum，这样做会使所有邻居节点的路径被累加 
                for (int i = 0; i < num[a].size(); i++) {
            int next = num[a][i].first;
            if (b == next) continue;
            int w = num[a][i].second;
            res = max(res, sum + w); // 注意这里不要把sum+w直接赋值给sum，因为for循环遍历到下一轮的时候需要用到的是接口传进来的sum的原值、而不是每个分支的累加
            dfs(next, a, sum + w);
        }

#include <math.h>
#include <algorithm>
#include <iostream>
using namespace std;
class Solution {
  private:
      long long res;
      vector<pair<int, int>>num[100001]; // 注意定义类型为pair的vector的时候需要定义其长度，之后push back即为为其pair赋值
  public:
    // a表示当前到达的点，b表示搜索的上一个点
    void dfs(int a, int b, long long sum) {
        for (int i = 0; i < num[a].size(); i++) {
            int next = num[a][i].first;
            if (b == next) continue;
            int w = num[a][i].second;
            res = max(res, sum + w); // 注意这里不要把sum+w直接赋值给sum，因为for循环遍历到下一轮的时候需要用到的是接口传进来的sum的原值、而不是每个分支的累加
            dfs(next, a, sum + w);
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最终结果
     * @param n int整型 城市数量
     * @param u int整型vector
     * @param v int整型vector
     * @param w int整型vector
     * @return long长整型
     */
    long long solve(int n, vector<int>& u, vector<int>& v, vector<int>& w) {
        // write code here
        res = 0;
        for(int i = 0; i < n - 1; i++) {
            num[u[i]].push_back({v[i], w[i]});
            num[v[i]].push_back({u[i], w[i]});
        }
        for (int i = 1; i < n + 1; i++) {
            if (num[i].size() == 1) {
                dfs(i, i, 0);
            }
        }
        return res;
    }
};