Leetcode 2467. Most Profitable Path in a Tree

[Woodyiiiiiii]

这道题不难，但主要是麻烦。

1. 首先找到Bob的移动路径，看到题目是undirected tree，所以只有一条。
2. 使用DFS去同步移动A和Bob节点，计算profit。注意使用回溯法的时候记得回归变量。DFS与单纯抽出路径一个个比较的好处是分支变少了。

图的问题中，为了避免深度/广度遍历中环的出现(预处理得到双边关系的map)，有以下方法：

1. 方法中记录上一个节点
2. 使用访问数组

class Solution {
    
    int ans = Integer.MIN_VALUE;

    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        // convert edges to graph
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            if (!graph.containsKey(edge[0])) {
                graph.put(edge[0], new ArrayList<>());
            }
            graph.get(edge[0]).add(edge[1]);
            if (!graph.containsKey(edge[1])) {
                graph.put(edge[1], new ArrayList<>());
            }
            graph.get(edge[1]).add(edge[0]);
        }

        // record the paths that b node move to zero node
        // the size of pathsOfB is 1 constantly
        List<List<Integer>> pathsOfB = new ArrayList<>();
        DFSOfB(graph, -1, bob, new ArrayList<>(), pathsOfB);
        List<Integer> pathB = pathsOfB.get(0);

        // DFS of A node
        DFSOfA(graph, -1, 0, 0, 0, pathB, amount);

        return ans;
    }

    private void DFSOfB(final Map<Integer, List<Integer>> graph, int preNode, int node, List<Integer> path, List<List<Integer>> paths) {
        path.add(node);

        if (node == 0) {
            paths.add(new ArrayList<>(path));
            return;
        }

        for (int next : graph.get(node)) {
            if (next == preNode) {
                continue;
            }
            DFSOfB(graph, node, next, path, paths);
        }

        path.remove(path.size() - 1);
    }

    private void DFSOfA(final Map<Integer, List<Integer>> graph, int preNode, int node, int profit, int level, List<Integer> pathB, int[] amount) {
        int preAmount = level < pathB.size() ? amount[pathB.get(level)] : 0;
        if (level < pathB.size()) {
            int curB = pathB.get(level);
            if (curB == node) {
                amount[curB] = amount[curB] / 2;
            } else {
                amount[curB] = 0;
            }
        }
        profit += amount[node];

        if (graph.get(node).size() == 1 && node != 0) {
            ans = Math.max(ans, profit);
        }

        for (int next : graph.get(node)) {
            if (next == preNode) {
                continue;
            }
            DFSOfA(graph, node, next, profit, level + 1, pathB, amount);
        }

        if (level < pathB.size()) {
            amount[pathB.get(level)] = preAmount;
        }
    }
    
}

---

• https://leetcode.com/problems/most-profitable-path-in-a-tree/