反复横跳

思路

首先假设固定起始点分别为 , ，设 为所有边权之和，通过贪心可以发现，当完成任务时，除起点到终点的这条路径只经历一次外，其余每条边都要经历两次时路径和最短，此时答案为 （ 表示 ，两点间的路径和）。当 最大时答案最小，由此可以推出，当选择在树上最长路径的一端作为起点，另一端作为终止点时，所经历的路径最短。
可以通过两次 求出树上最长路径。
时间复杂度：

Code

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

class Solution {
#define maxn 100010
private:
    vector<pair<int,int>> g[maxn];

public:
    /**
     * 最短距离
     * @param n int整型
     * @param Edge Point类vector
     * @param val int整型vector
     * @return long长整型
     */
    void dfs1(int x, int fa, long long sum, int &point, long long &dis) {
        if (sum > dis) {
            point = x;
            dis = sum;
        }
        for (auto cur: g[x]) {
            int v = cur.first, w = cur.second;
            if (v == fa) continue;
            dfs1(v, x, sum + w, point, dis);
        }
    }

    long long dfs2(int x, int fa = 0) {
        long long res = 0;
        for (auto cur: g[x]) {
            int v = cur.first, w = cur.second;
            if (v == fa) continue;
            res = max(res, dfs2(v, x) + w);
        }
        return res;
    }

    long long solve(int n, vector<Point>& Edge, vector<int>& val) {
        // write code here
        for (int i = 1; i <= n; ++i)
            g[i].clear();
        long long ans = 0;

        for (int i = 1; i < n; ++i) {
            g[Edge[i-1].x].push_back({Edge[i-1].y, val[i-1]});
            g[Edge[i-1].y].push_back({Edge[i-1].x, val[i-1]});
            ans += val[i-1];
        }

        ans <<= 1;
        int point = 1;
        long long dis = 0;
        dfs1(1, 0, 0, point, dis);
        // cout << "Ponit: " << point << endl;
        ans -= dfs2(point, 0);

        return ans;
    }
};