题解 | #反复横跳#

题目的主要信息：

一张带权无向图，图中任意两点间有且仅有一条路径，这是一棵无向树
计算从任意点出发并访问完所有节点经过边的权值之和的最小值

分析：

首先，如果我们要从一个点到达其他所有点，每条边我们必须经过一次，因为任意两点之间有且仅有一条路径。然后，因为可以到树叶以后再回溯访问，再到另外的枝，因此两倍权值总和必定可以访问完所有的节点。因此我们要的是从一个点到其他所有节点经过路径权值和最小，我们就要让重复经过的部分最小，即非重复经过的部分最大。我们试想，如果我们从树的直径的一端到另一端开始访问，那我们回溯部分就会少了直径的长度，非重复部分就是树的一点到另一点的最长距离，这样我们就可以求得最小值。
因此，最终答案就是2倍权值总和-树直径长度
图片说明

方法一：两次dfs求直径法

具体做法：
构建图的时候顺序累加两倍边长，然后利用两次dfs求树的直径，求树直径具体方法可以参考树的直径这道题。最后两倍边长和减去树的直径长度即可。
图片说明
这个方法bfs也可以做，具体同样参考前面这道题的题解。

class Solution {
public:
    //深度优先函数
    void dfs(vector<vector<pair<int, int>>>& G, vector<int>& res, int start, int pre, int length){
        for(int i = 0; i < G[start].size(); i++){ //遍历与这个点相连的每一条边
            if(G[start][i].first != pre){
                length += G[start][i].second;
                if(length > res[0]){
                    res[0] = length;
                    res[1] = G[start][i].first;
                }
                dfs(G, res, G[start][i].first, start, length);
                length = length - G[start][i].second; //回溯
            }
        }
    }
    long long solve(int n, vector<Point>& Edge, vector<int>& val) {
        vector<vector<pair<int, int> > > G(n + 1); //记录图的连接表和边的权值
        long long res = 0;
        for(int i = 0; i < Edge.size(); i++){
            res += 2 * val[i]; //整个图所有边的两倍权值
            G[Edge[i].x].push_back(make_pair(Edge[i].y, val[i]));
            G[Edge[i].y].push_back(make_pair(Edge[i].x, val[i]));
        }
        //两次dfs求直径
        vector<int> length(2, 0);  //第一个零表示以第0个结点为起点的最长路径长度，第二个零表示最长路径的重点序列
        dfs(G, length, 1, 0, 0);   //从0结点深度优先找最远距离
        vector<int> diameter(2, 0);
        dfs(G, diameter, length[1], 0, 0); //以刚刚找到的最远距离再次深度优先找最元距离即是答案
        return res - diameter[0]; 
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，两次dfs分别最多访问 $n$ 个节点
空间复杂度： $O(n)$ ，递归栈最深长度为 $n$ ，保存图的矩阵最多有 $2n$ 个元素，其余变量都是常数级

方法二：树型dp求直径

具体做法：
我们不妨假设 $1$ 号节点为根节点，将其看成一棵有根树。设 $dp[x$ ]表示从节点 $x$ 出发，往以 $x$ 为根的子树走，能够到达的最远距离。设 $x$ 的子节点分别为 $y_1$ , $y_2$ , $y_3$ ,..., $y_i$ ， $e(x,y)$ 表示从 $x$ 到 $y$ 的边权，则可以得到状态转移方程： $dp[x]=max(dp[y_i]+e(x,y_i))$
然后，我们考虑对于每个节点 $x$ 求出经过 $x$ 的最长链的长度 $F[x]$ ,整棵树的直径就是 $max(F[x])(1<=x<=n)$ 。
对于任意两个节点 $y_i$ 和 $y_j$ ，经过节点 $x$ 的最长链的长度可以通过四个部分来构成：

$dp[y_i]$
$dp[y_j]$
$e(x,y_i)$
$e(x,y_j)$

则 $F[x]=max(dp[y_i]+dp[y_j]+e(x,y_i)+e(x,y_j))$
用递归遍历每一个节点就可以求得。

class Solution {
public:
    int diameter = 0;
    void treeDp(int cur, vector<vector<pair<int, int>>>& G, vector<int>& dp, vector<bool>& vis){
        vis[cur] = true; //记录访问过
        for(int i = 0; i < G[cur].size(); i++){
            if(vis[G[cur][i].first])
                continue;
            treeDp(G[cur][i].first, G, dp, vis); //先递归求子节点
            //更新直径和当前节点
            diameter = max(diameter, dp[cur] + dp[G[cur][i].first] + G[cur][i].second);
            dp[cur] = max(dp[cur], dp[G[cur][i].first] + G[cur][i].second);
        }
    }
    long long solve(int n, vector<Point>& Edge, vector<int>& val) {
        vector<vector<pair<int, int> > > G(n + 1); //记录图的连接表和边的权值
        long long res = 0;
        for(int i = 0; i < Edge.size(); i++){
            res += 2 * val[i]; //整个图所有边的两倍权值
            G[Edge[i].x].push_back(make_pair(Edge[i].y, val[i]));
            G[Edge[i].y].push_back(make_pair(Edge[i].x, val[i]));
        }
        vector<bool> vis(n + 1, false); //记录节点是否访问过
        vector<int> dp(n + 1, 0); //树型dp记录从每个节点开始的最长链路
        treeDp(1, G, dp, vis);  //树型dp求树的直径
        return res - diameter;
    }
};

复杂度分析：

时间复杂度： $O(n)$ ，树中每个节点遍历一次
空间复杂度： $O(n)$ ，保存图的矩阵最多 $2n$ 个元素，其余辅助数组长度都是 $n$