树上最大得分和路径 图解题解

这道题到底在问什么

输入

edges=[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], bob=6, amount=[-4,2,8,6,-10,10,12]

输出

10

输入

edges=[[0,1]], bob=1, amount=[-7280,2350]

输出

-7280

最优解：一步一步想明白

1. 3记牢这套:一遍标 Bob 的时间戳,一遍让 Alice 按时间比门。先小于就抢先、相等就平分、大于就落空。下面先把 Bob 的时间戳标出来。
2. 4Alice 起点 0,Bob 起点 6先看清这棵树。根 0 在最上面,它有两个孩子 1 和 2,1 又带着叶子 3、4,2 又带着叶子 5、6。Alice 站在根 0,标成紫色;Bob 站在叶子 6,标成红色。接下来他俩各自出发,Alice 往下钻找叶子,Bob 往上爬奔根 0。
3. 5叶子 = 3,4,5,6Alice 最终一定停在某片叶子上,这棵树的叶子是 3、4、5、6,对应四条从根出发的路。她要在这四条里挑净得分最高的一条。分值受一件事影响:每扇门是不是被 Bob 抢先开了。所以我们得先知道 Bob 什么时候到哪儿。
4. 6计划:dfs1 标 ts → dfs2 结算整道题拆成两步。第一步让 Bob 先动:从他所在的 6 号点出发,找到通往根 0 的唯一一条路,把这条路上每个点标上时间戳。第二步再让 Alice 从根往下走,拿她的到达时间和这些时间戳比。我们先把所有点的时间戳都当成无穷大,再往 Bob 走过的点上填真实值。
5. 7ts[6] = 0Bob 从 6 号点出发,第 0 秒他就站在这里,所以 6 号点的时间戳记成 0。时间戳的含义就是:Bob 最早在第几秒踏上这个点。他要奔根 0,6 只跟 2 相连,于是下一步只能走到 2。
6. 8ts[2] = 1Bob 从 6 迈一步到 2,这是第 1 秒,所以 2 号点的时间戳记成 1。走过的 6 号点标成蓝色,表示时间戳已经盖好。2 号点上面连着根 0,Bob 继续往上爬。
7. 9ts[0] = 2 · Bob 到根停Bob 从 2 再迈一步到根 0,这是第 2 秒,时间戳记成 2。规则说 Bob 一到根 0 就停下不再动。到这里 Bob 的整条路线 6、2、0 三个点的时间戳全部盖好了,分别是 0、1、2。
8. 101,3,4,5 的 ts = 无穷大Bob 的路只碰到 6、2、0 这三个点。1、3、4、5 这几个点 Bob 根本不会经过,它们的时间戳一直是当初设的无穷大。无穷大是个很关键的信号:它表示 Bob 永远走不到这里,所以 Alice 到了一定是先开门,能独享整份分。
9. 11ts = [2, ∞, 1, ∞, ∞, ∞, 0]把七个点的时间戳汇总:ts[0] 是 2、ts[2] 是 1、ts[6] 是 0,这三点在 Bob 路上;ts[1]、ts[3]、ts[4]、ts[5] 都是无穷大。第一步到此结束。接下来第二步,Alice 从根 0 往下走,每到一个点就拿她的到达秒数去和这张表比。
10. 12t = 0 相对 ts = 2 → Alice 抢先Alice 出发,第 0 秒她就在根 0。根 0 的时间戳是 2,也就是 Bob 要第 2 秒才到。Alice 的 0 比 2 小,她抢先开了这扇门,整份分归她。0 号门的分值是 -4。
11. 13v = 0 加 (-4) = -4把 0 号门的 -4 加进这条路的得分,v 从 0 变成 -4。根 0 标成绿色表示 Alice 已经拿过它的分。根有两个孩子 1 和 2,按顺序先走 1 这一支。
12. 14t = 1 相对 ts = ∞ → Alice 抢先Alice 走到 1,这是第 1 秒。1 号点不在 Bob 的路上,时间戳是无穷大,Alice 的 1 当然更小,她抢先开门。1 号门分值是 2。
13. 15v = -4 加 2 = -21 号门的 2 加进来,v 从 -4 变成 -2。1 号点变绿。它带着两片叶子 3 和 4,先钻左边的 3。
14. 16叶子 3 候选 = 4到叶子 3,第 2 秒。它 ts 是无穷大,Alice 抢先,独享 6,v 从 -2 变成 4。3 是叶子,Alice 到这就停了。这条 0 到 1 到 3 的路走完,得分 4,记成第一个候选。
15. 17叶子 4 候选 = -12回到 1,换走另一片叶子 4,还是第 2 秒。4 也不在 Bob 路上,Alice 独享它的门,可这门分值是 -10,是扣分。v 从 1 号点走下来的 -2 变成 -12。这条 0 到 1 到 4 的路得分只有 -12,远不如走 3。
16. 18回到根 0,v 复位到 -41 这一支两片叶子都试过了,得分是 4 和 -12。DFS 回到根 0,注意得分 v 会退回根这里的 -4,因为换路要从根重新往下累加。现在走根的另一个孩子 2。前面 2 号点的时间戳是 1,好戏来了。
17. 19t = 1 相等 ts = 1 → 平分Alice 第 1 秒走到 2,而 Bob 的时间戳也正好是 1。两人同一秒撞到同一扇门,规则说这时平分。2 号门分值是 8,平分就是各拿一半,Alice 只加 8 的一半。
18. 20v = -4 加 4 = 08 的一半是 4,加进来 v 从 -4 变成 0。这就是平分:同一秒到,分值对半分。2 号点变绿。它带着叶子 5 和 6,先走 5。
19. 21叶子 5 候选 = 10 ← 最好走到叶子 5,第 2 秒。5 不在 Bob 路上,Alice 独享 10,v 从 0 变成 10。这条 0 到 2 到 5 的路得分 10,比前面所有候选都高,当前最好成绩刷新成 10。
20. 22t = 2 大于 ts = 0 → 落空回到 2 换走叶子 6。Alice 第 2 秒才到 6,可 Bob 的时间戳是 0,他一开始就在这里、早把门开了。门开过就不再计分,Alice 到 6 这一格一分都拿不到。哪怕 6 号门写着 12 的加分,也和她无关。
21. 23叶子 6 候选 = 06 号门落空,加 0,这条 0 到 2 到 6 的路得分停在 0。它是个候选 0,但比不过走 5 的 10。最好成绩仍然是 10。四片叶子全试完了。
22. 24最大 = 10把四片叶子的成绩摆一起:走 3 得 4,走 4 得 -12,走 5 得 10,走 6 得 0。取最大的,答案就是 10,对应 Alice 走 0 到 2 再到 5 这一条。
23. 25答案 = 10高亮这条最优路 0 到 2 到 5:根 0 抢先拿 -4,到 2 和 Bob 平分拿 4,到叶子 5 抢先拿 10,合起来 -4 加 4 加 10 正好是 10。整道题就是一遍标 Bob 时间戳,一遍让 Alice 按时间比门取最大。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def mostProfitablePath(
        self, edges: List[List[int]], bob: int, amount: List[int]
    ) -> int:
        def dfs1(i, fa, t):
            if i == 0:
                ts[i] = min(ts[i], t)
                return True
            for j in g[i]:
                if j != fa and dfs1(j, i, t + 1):
                    ts[j] = min(ts[j], t + 1)
                    return True
            return False

        def dfs2(i, fa, t, v):
            if t == ts[i]:
                v += amount[i] // 2
            elif t < ts[i]:
                v += amount[i]
            nonlocal ans
            if len(g[i]) == 1 and g[i][0] == fa:
                ans = max(ans, v)
                return
            for j in g[i]:
                if j != fa:
                    dfs2(j, i, t + 1, v)

        n = len(edges) + 1
        g = defaultdict(list)
        ts = [n] * n
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        dfs1(bob, -1, 0)
        ts[bob] = 0
        ans = -inf
        dfs2(0, -1, 0, 0)
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        int n = edges.size() + 1;
        vector<vector<int>> g(n);
        for (auto& e : edges) {
            int a = e[0], b = e[1];
            g[a].emplace_back(b);
            g[b].emplace_back(a);
        }
        vector<int> ts(n, n);
        function<bool(int i, int fa, int t)> dfs1 = [&](int i, int fa, int t) -> bool {
            if (i == 0) {
                ts[i] = t;
                return true;
            }
            for (int j : g[i]) {
                if (j != fa && dfs1(j, i, t + 1)) {
                    ts[j] = min(ts[j], t + 1);
                    return true;
                }
            }
            return false;
        };
        dfs1(bob, -1, 0);
        ts[bob] = 0;
        int ans = INT_MIN;
        function<void(int i, int fa, int t, int v)> dfs2 = [&](int i, int fa, int t, int v) {
            if (t == ts[i])
                v += amount[i] >> 1;
            else if (t < ts[i])
                v += amount[i];
            if (g[i].size() == 1 && g[i][0] == fa) {
                ans = max(ans, v);
                return;
            }
            for (int j : g[i])
                if (j != fa) dfs2(j, i, t + 1, v);
        };
        dfs2(0, -1, 0, 0);
        return ans;
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private List<Integer>[] g;
    private int[] amount;
    private int[] ts;
    private int ans = Integer.MIN_VALUE;

    public int mostProfitablePath(int[][] edges, int bob, int[] amount) {
        int n = edges.length + 1;
        g = new List[n];
        ts = new int[n];
        this.amount = amount;
        Arrays.setAll(g, k -> new ArrayList<>());
        Arrays.fill(ts, n);
        for (int[] e : edges) {
            int a = e[0], b = e[1];
            g[a].add(b);
            g[b].add(a);
        }
        dfs1(bob, -1, 0);
        ts[bob] = 0;
        dfs2(0, -1, 0, 0);
        return ans;
    }

    private boolean dfs1(int i, int fa, int t) {
        if (i == 0) {
            ts[i] = Math.min(ts[i], t);
            return true;
        }
        for (int j : g[i]) {
            if (j != fa && dfs1(j, i, t + 1)) {
                ts[j] = Math.min(ts[j], t + 1);
                return true;
            }
        }
        return false;
    }

    private void dfs2(int i, int fa, int t, int v) {
        if (t == ts[i]) {
            v += amount[i] >> 1;
        } else if (t < ts[i]) {
            v += amount[i];
        }
        if (g[i].size() == 1 && g[i].get(0) == fa) {
            ans = Math.max(ans, v);
            return;
        }
        for (int j : g[i]) {
            if (j != fa) {
                dfs2(j, i, t + 1, v);
            }
        }
    }
}

复杂度

面试官可能追问