题解 | #反复横跳#

题意整理：

基本题意

给出一棵具有 $n$ 个结点的无根树，给出每条边的边权 $f_i$ ，表示两个结点之间的距离。

可以任意选择一个结点作为起点，按照一定的顺序访问每个结点至少一次，问经过的路径的总长度最少是多少。输出这个答案。

数据范围与性质

$1\le n \le 10^5, i< a_i \le n$ 。

$1 \le f_i \le 10^5$ 。

注意最后的答案是 $O(\sum f_i)$ 的，因此可能超出 $\text{int}$ 范围。

求解目标的转化

我们的路径会经历若干条边。

我们可以简单推断出，题目求解的方案中，每条边至少经过 $1$ 次。证明如下：

每条边经过至少 $1$ 次： 反证法。如果存在一条边没有被经过，那么不妨在树上断掉这条边，树就分裂成了两个联通块，不可能存在一条路径一次性访问过所有结点。

我们考虑一下最优的路径方案是什么样的。

最优路径一定具有一个起点，我们令其为 $root$ ，并且把这棵树看成以 $root$ 为根的有根树。

我们要从 $root$ 出发，访问整颗子树的每个结点至少一次。

然后接下来，该路径一定会从 $root$ 出发走向其一个未访问过的子结点 $v$ （如果存在的话），走到 $v$ 之后，我们可以把接下来的流程看成一个子问题：从 $v$ 出发，访问以 $v$ 为根的子树每个结点至少一次（图1）。

图片说明

图 1

然后接下来，访问以 $v$ 为根的子树完毕后，有两种可能：一个是从 $v$ 回到 $root$ ，然后继续考虑从 $root$ 访问其他子结点的流程（图2）。

图片说明

图 2 、

另一个，如果 $v$ 是从 $root$ 出发访问的最后一个子结点，说明其他子结点的子树都已经被访问完毕了，那么我们可以不必从 $v$ 回到 $root$ 了。

图片说明

图 3

因此，如果根结点选定，从上至下分析可知：最后一个结点访问之后，不需要再向上回溯 (图3) ，因此找出一个深度（距离根结点的距离，用 $dep$ 表示）最大的叶子结点 $l$ ，那么 $(2\sum f_i) - dep(l)$ 就是以 $root$ 为根时最短的总路径长度。

由于根结点 $root$ 可以任意选，而对于任意的 $dep(l)$ 都可以看作是两端分别为 $root,l$ 的一条树链。我们要最小化答案，其实就是最大化 $dep(l)$ ，也就是找到树上的最长树链。

于是我们的求解目标转为了一个经典的树上问题——树上最长链问题，即树的直径。

于是这道题的大致思路：找出树的直径 $L$ ，最后输出答案为 $(2\sum f_i) - L$ 。

解法1：暴力换根搜索

【知识点】树的遍历， $\text{dfs}$

【算法】简单的搜索

实现与分析

树上的路径只有 $O(n^2)$ 条，我们不妨枚举所有的起点，然后从起点出发遍历整棵树，求出起点。

采用 $\text{dfs}$ 即可，用 $dep(i)$ 表示起点到 $i$ 的距离，对于结点 $i$ 的子结点 $v$ ，有 $dep(v)=dep(i)+f(i,v)$ ，其中 $f(i,v)$ 表示从 $i$ 到 $v$ 的边的长度。

具体细节见代码。

参考代码（会 TLE，通过13/15的数据）

/**
 * struct Point {
 *    int x;
 *    int y;
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 最短距离
     * @param n int整型 
     * @param Edge Point类vector 
     * @param val int整型vector 
     * @return long长整型
     */
    static const int MAXN = 110000;
    vector <int> son[MAXN];//用于存放每个点链接的结点
    vector <int> edge_len[MAXN];//用于存放对应边的长度
    long long dep[MAXN];

    void dfs(int x,int fa)//存父亲结点防止向父亲结点递归
    {
        for(int i=0;i<son[x].size();i++)
        {
            int v=son[x][i];
            if(v==fa)continue;
            dep[v]=dep[x]+edge_len[x][i];//求出 v 的dep
            dfs(v,x);//递归
        }
    }

    long long solve(int n, vector<Point>& Edge, vector<int>& val) {
        // write code here
        long long ret=0;
        long long lenth=0;//用于存放最长链长度

        for(int i=0;i<Edge.size();i++)//建图,双向边.包括边的指向和边长.
        {
            son[Edge[i].x].push_back(Edge[i].y);
            son[Edge[i].y].push_back(Edge[i].x);
            edge_len[Edge[i].x].push_back(val[i]);
            edge_len[Edge[i].y].push_back(val[i]);
            ret += 2*val[i];//先累加所有边权的两倍到 ret 上
        }

        for(int i=1;i<=n;i++)
        {
            dep[i]=0;//以i为根,因此其dep初始化为0
            dfs(i,0);//求解所有结点的 dep
            for(int j=1;j<=n;j++)
                lenth=max(lenth,dep[j]);//保留最长链到变量 lenth 中
        }

        return ret-lenth;//返回答案
    }
};

因为从每个起点遍历整棵树是 $O(n)$ 的，需要枚举 $n$ 个不同的起点，因此时间复杂度是 $O(n^2)$ ，思路简单，但会超时。因为每次遍历可以重复使用数组，并且 $\text{dfs}$ 深度最大达到 $O(n)$ 因此只达到 $O(n)$ 的空间复杂度。

解法2：树dp

【算法】树的遍历，动态规划

实现与分析

树上dp是树的直径的一种经典解法。

首先我们把这棵树看作是以 $1$ 为根的有根树。

我们的答案是求解最长树上路径，而所有的树上路径都可以看作两个端点 $x,y$ 之间的简单路径，并且路径一定经过两者的 $\text{lca}$ （最近公共祖先） $z$ （图4）。

图片说明

图4

那么，树上每个点作为 $\text{lca}$ 的时候，经过它的最长路径，就是在其子结点中选两个向下延伸路径最长的，然后把两条路径拼起来。将树上每个点作为 $\text{lca}$ 考虑之后，取其中最长的路径，就是答案了。

我们考虑通过 $\text{dp}$ 处理再计算的方式求解每个结点作为 $\text{lca}$ 的最长路径长度。

状态设计：

定义 $dp(i)$ 表示在以结点 $i$ 为根的子树中，从 $i$ 出发的最长简单路径的长度。

特殊地，如果不存在满足定义的路径，则取值为 $0$ 。

状态转移：

$dp(i)=\max\{dp(v)+f(i,v)\}$ ，其中 $v$ 是 $i$ 的子结点， $f(i,v)$ 表示从 $i$ 到 $v$ 的边的长度。

答案构造：

令 $v_1,v_2,...v_k$ 表示 $i$ 的子结点，并且它们已经按照 $dp(v_1)+f(i,v_1)\le dp(v_2)+f(i,v_2)\le ... \le dp(v_k)+f(i,v_k)$ 排好了序。

那么显然， $dp(v_1)+f(i,v_1)+dp(v_2)+f(i,v_2)$ 就是结点 $i$ 作为 $\text{lca}$ 的最长路径长度。

通过树上 $\text{dfs}$ 实现即可。

参考代码（时间复杂度 $O(n\log n)$ ）

/**c++
 * struct Point {
 *    int x;
 *    int y;
 * };
 */
#include <vector>
#include <algorithm>
class Solution {
public:
    /**
     * 最短距离
     * @param n int整型 
     * @param Edge Point类vector 
     * @param val int整型vector 
     * @return long长整型
     */
    static const int MAXN = 110000;
    vector <int> son[MAXN];//用于存放每个点连接的结点
    vector <int> edge_len[MAXN];//用于存放对应边的长度
    long long lenth=0;//用于存放最长链长度
    long long dp[MAXN];//dp数组

    static bool cmp(int x,int y)//从大到小排序
    {
        return x>y;
    }

    void dfs(int x,int fa)//存父亲结点防止向父亲结点递归
    {
        for(int i=0;i<son[x].size();i++)
        {
            int v=son[x][i];
            if(v==fa)continue;
            dfs(v,x);//递归
            dp[x]=max(dp[x],dp[v]+edge_len[x][i]);//状态转移
        }

        for(int i=0;i<son[x].size();i++)//把子结点改成其dp值+到x的边权，然后排序取最大的两个。
            if(son[x][i]==fa)
                son[x][i]=-1;
            else
                son[x][i] = dp[son[x][i]] + edge_len[x][i];

        sort(son[x].begin(),son[x].end(),cmp);
        if(fa)son[x].pop_back();//把父亲结点的影响删除

        if(son[x].size()>=2)//更新答案。细节，不能越界。
            lenth=max(lenth,0ll+son[x][0]+son[x][1]);
        else if(son[x].size()>=1)
            lenth=max(lenth,0ll+son[x][0]);
    }

    long long solve(int n, vector<Point>& Edge, vector<int>& val) {
        // write code here
        long long ret=0;
        lenth=0;
        memset(dp,0,sizeof(dp));//初始化dp数组

        for(int i=0;i<Edge.size();i++)//建图,双向边.包括边的指向和边长.
        {
            son[Edge[i].x].push_back(Edge[i].y);
            son[Edge[i].y].push_back(Edge[i].x);
            edge_len[Edge[i].x].push_back(val[i]);
            edge_len[Edge[i].y].push_back(val[i]);
            ret += 2*val[i];//先累加所有边权的两倍到 ret 上
        }

        dfs(1,0);

        return ret-lenth;//返回答案
    }
};

只需要遍历一遍树， $\text{dfs}$ 深度最大是 $O(n)$ 的，总空间复杂度 $O(n)$ 。但是如果要对子结点排序，时间复杂度可达 $O(n\log n)$ ，但也可以扫描两遍子结点取最大的两个值，时间复杂度 $O(n)$ .

题解 | #反复横跳#

题意整理：

基本题意

数据范围与性质

求解目标的转化

解法1：暴力换根搜索

实现与分析

参考代码（会 TLE，通过13/15的数据）

解法2：树dp

实现与分析

参考代码（时间复杂度 ）

参考代码（时间复杂度 $O(n\log n)$ ）