一夜暴富

3妹：2哥2哥，你有没有看到新闻， 有人中了2.2亿彩票大奖！
2哥 : 看到了，2.2亿啊， 一生一世也花不完。
3妹：为啥我就中不了呢，不开心呀不开心。
2哥 : 得了吧，你又不买彩票，还是脚踏实地的好~
3妹：小富靠勤，中富靠德，大富靠命， 可能是我命不好。
2哥 : 话说如果你有了钱，想要干嘛呀？
3妹：旅行，到处去旅行
2哥：就知道会有这一项， 我今天看到一个关于旅行的题目，让我也来考考你吧~

考考你

题目：

现有一棵无向、无根的树，树中有 n 个节点，按从 0 到 n - 1 编号。给你一个整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条边。

每个节点都关联一个价格。给你一个整数数组 price ，其中 price[i] 是第 i 个节点的价格。

给定路径的 价格总和 是该路径上所有节点的价格之和。

另给你一个二维整数数组 trips ，其中 trips[i] = [starti, endi] 表示您从节点 starti 开始第 i 次旅行，并通过任何你喜欢的路径前往节点 endi 。

在执行第一次旅行之前，你可以选择一些 非相邻节点 并将价格减半。

返回执行所有旅行的最小价格总和。

示例 1：

image.png

输入：n = 4, edges = [[0,1],[1,2],[1,3]], price = [2,2,10,6], trips = [[0,3],[2,1],[2,3]]
输出：23
解释：
上图表示将节点 2 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 、2 和 3 并使其价格减半后的树。
第 1 次旅行，选择路径 [0,1,3] 。路径的价格总和为 1 + 2 + 3 = 6 。
第 2 次旅行，选择路径 [2,1] 。路径的价格总和为 2 + 5 = 7 。
第 3 次旅行，选择路径 [2,1,3] 。路径的价格总和为 5 + 2 + 3 = 10 。
所有旅行的价格总和为 6 + 7 + 10 = 23 。可以证明，23 是可以实现的最小答案。

示例 2：

image.png

输入：n = 2, edges = [[0,1]], price = [2,2], trips = [[0,0]]
输出：1
解释：
上图表示将节点 0 视为根之后的树结构。第一个图表示初始树，第二个图表示选择节点 0 并使其价格减半后的树。
第 1 次旅行，选择路径 [0] 。路径的价格总和为 1 。
所有旅行的价格总和为 1 。可以证明，1 是可以实现的最小答案。

提示：

1 <= n <= 50
edges.length == n - 1
0 <= ai, bi <= n - 1
edges 表示一棵有效的树
price.length == n
price[i] 是一个偶数
1 <= price[i] <= 1000
1 <= trips.length <= 100
0 <= starti, endi <= n - 1

思路：

思考

深度优先搜索 + 动态规划,
为了使旅行的价格总和最小，那么每次旅行的路径必定是最短路径。根据题意，每次旅行 trips[i] 都是独立的，因此我们可以依次开始旅行 trips[i]，并且用数组 count记录节点在旅行中被经过的次数。记旅行 trips[i]的起点和终点分别为 starti和 endi，那么我们以 starti为树的根节点，对树进行深度优先搜索，对于如果节点 node\textit{node}node 的子树（包含它本身）包含节点 endi ，那么我们将 count[node] 加一。

java代码：

class Solution {
    private List<Integer>[] g, qs;
    private int[] diff, father, color, price;

    public int minimumTotalPrice(int n, int[][] edges, int[] price, int[][] trips) {
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (var e : edges) {
            int x = e[0], y = e[1];
            g[x].add(y);
            g[y].add(x); // 建树
        }

        qs = new ArrayList[n];
        Arrays.setAll(qs, e -> new ArrayList<>());
        for (var t : trips) {
            int x = t[0], y = t[1];
            qs[x].add(y); // 路径端点分组
            if (x != y) qs[y].add(x);
        }

        pa = new int[n];
        for (int i = 1; i < n; ++i)
            pa[i] = i;

        diff = new int[n];
        father = new int[n];
        color = new int[n];
        tarjan(0, -1);

        this.price = price;
        var p = dfs(0, -1);
        return Math.min(p[0], p[1]);
    }

    // 并查集模板
    private int[] pa;

    private int find(int x) {
        if (pa[x] != x)
            pa[x] = find(pa[x]);
        return pa[x];
    }

    private void tarjan(int x, int fa) {
        father[x] = fa;
        color[x] = 1; // 递归中
        for (int y : g[x])
            if (color[y] == 0) { // 未递归
                tarjan(y, x);
                pa[y] = x; // 相当于把 y 的子树节点全部 merge 到 x
            }
        for (int y : qs[x])
            // color[y] == 2 意味着 y 所在子树已经遍历完
            // 也就意味着 y 已经 merge 到它和 x 的 lca 上了
            if (y == x || color[y] == 2) { // 从 y 向上到达 lca 然后拐弯向下到达 x
                ++diff[x];
                ++diff[y];
                int lca = find(y);
                --diff[lca];
                int f = father[lca];
                if (f >= 0) {
                    --diff[f];
                }
            }
        color[x] = 2; // 递归结束
    }

    private int[] dfs(int x, int fa) {
        int notHalve = 0, halve = 0, cnt = diff[x];
        for (int y : g[x])
            if (y != fa) {
                var p = dfs(y, x); // 计算 y 不变/减半的最小价值总和
                notHalve += Math.min(p[0], p[1]); // x 不变，那么 y 可以不变，可以减半，取这两种情况的最小值
                halve += p[0]; // x 减半，那么 y 只能不变
                cnt += p[2]; // 自底向上累加差分值
            }
        notHalve += price[x] * cnt; // x 不变
        halve += price[x] * cnt / 2; // x 减半
        return new int[]{notHalve, halve, cnt};
    }
}