题目的主要信息：

已知带权无向图，每个节点之间仅有一条路径
求经过所有节点最小权重之和

方法一：DFS

如果不考虑路径长度，那么把所有路径走一遍必定可以经过所有节点。 alt 要经过每一个节点，且每个节点之间只有一条路径，那么至少需要把所有的路径走一遍，假设权重之和为weight。在最坏的情况，每条路径都需要走两遍才能遍历所有节点，权重之和为2weight。最优解在[weight,2weight]范围中。如上图所示，在这种做法每段路径都重复走了一遍，如果能把重复路径的权重和最小化，即最大化只有一遍的路径权重之和。因此，我们需要找到从树的一端到另一端最长的路径，把这条最长不回溯路径长度剔除后，才是我们要的经过所有节点最小权重之和。 alt 寻找最长路径可以使用DFS递归。

具体做法：

/**
 * struct Point {
 *	int x;
 *	int y;
 * };
 */

struct connection{//邻接节点和两点之间的权重
    int node;
    int length;
};
class Solution {
public:
    vector<vector<connection>> G;//邻接矩阵
    long long max_length = 0;//最长路径
    int far_node;//最远的节点
    void DFS(int node, int pre_node, long long dist){
        if(dist>max_length){//保留最长路径
            max_length = dist;
            far_node = node;
        }
        for(int i=0;i<G[node].size();i++){//从node的邻接节点（除了pre_node）找最长路径的下一个节点
            if(G[node][i].node!=pre_node){
                DFS(G[node][i].node, node, dist+G[node][i].length);//递归计算最长路径
            }
        }
    }
    long long solve(int n, vector<Point>& Edge, vector<int>& val) {
        long long ans=0;
        G.resize(n,vector<connection>());
        for(int i=0;i<Edge.size();i++){
            ans += 2*val[i];//计算两倍权重值
            G[Edge[i].x-1].push_back({Edge[i].y-1,val[i]});//建立邻接矩阵
            G[Edge[i].y-1].push_back({Edge[i].x-1,val[i]});
        }
        DFS(0,-1,0);//从节点1出发，找距离节点1最远的节点far_node和最长路径max_length
        max_length=0;
        DFS(far_node,-1,0);//再从最远的节点far_node出发，找这棵树上的最长路径
        ans -= max_length;
        return ans;
        
    }
};

复杂度分析：

时间复杂度： $O (n)$ ，递归至多经过每一个节点一次，总共是n次。
空间复杂度： $O (n)$ ，递归栈至多大小为n。

方法二：暴力遍历（13/15组用例通过）

和方法一类似，还有一种最朴素的暴力方法，让每个节点都成为根节点一次，递归计算其他节点到根节点的距离，再从中比较出最长的距离。

具体做法：

struct connection{//邻接节点和两点之间的权重
    int node;
    int length;
};
class Solution {
public:
    vector<vector<connection>> G;//邻接矩阵
    long long length[110000];//记录到每个节点的路径
    long long max_length=0;
    void DFS(int node, int pre_node){
        for(int i=0;i<G[node].size();i++){//从node的邻接节点（除了pre_node）更新距离
            if(G[node][i].node!=pre_node){
                length[G[node][i].node]=length[node]+G[node][i].length;//更新节点到根结点的距离
                DFS(G[node][i].node, node);//递归计算各节点和根结点的距离
            }
        }
    }
    long long solve(int n, vector<Point>& Edge, vector<int>& val) {
        long long ans=0;
        G.resize(n,vector<connection>());
        for(int i=0;i<Edge.size();i++){
            ans += 2*val[i];//计算两倍权重值
            G[Edge[i].x-1].push_back({Edge[i].y-1,val[i]});//建立邻接矩阵
            G[Edge[i].y-1].push_back({Edge[i].x-1,val[i]});
        }
        
        for(int i=0;i<n;i++){//逐个节点查找最大路径
            length[i]=0;
            DFS(i,-1);
            for(int j=1;j<=n;j++){
                max_length=max(max_length,length[j]);
            }
        }
        ans -= max_length;
        return ans;
        
    }
};

复杂度分析：

时间复杂度： $O (n^{2})$ ，在计算最大路径的时候进行了两层循环。
空间复杂度： $O (n)$ ，借助了n个空间记录每个节点到根节点的距离。

题解 | #反复横跳#

题目的主要信息：

方法一：DFS

方法二：暴力遍历（13/15组用例通过）