leetcode：6240. 树上最大得分和路径【两次dfs模拟 + 读题题 + 不要用list做py函数的参数！！】

题目截图

题目分析

• 记录每个点相邻的节点g = defaultdict(list)
• 记录除0外的所有叶子节点
• Alice可能有多条路径到叶子
• bob只有一条路径到0，一次dfs找出这条路径
• 并将bob路径中的遍历的时间标上序号，方便alice进行判断
• alice开始dfs，一边遍历一边记录当前路径的分数（根据bob的访问时间），如果到达叶子，更新ans即可

tle例子（使用list作为参数，耗时++）

class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        g = defaultdict(list)
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        leaves = []
        for node in g:
            if len(g[node]) == 1 and node != 0:
                leaves.append(node)
        leaves = set(leaves)
        leaves_bool = defaultdict(bool)
        for leaf in leaves:
            leaves_bool[leaf] = True
        # 先看看bob到0怎么走
        path = []
        flag = False
        def dfs1(cur, temp_path, fa):
            nonlocal flag, path
            if flag:
                return
            if cur == 0:
                path = temp_path[:]
                flag = True
                return
            for next in g[cur]:
                if next != fa:
                    dfs1(next, temp_path + [next], cur)
        dfs1(bob, [bob], -1)
        bob_step = defaultdict(int)
        bob_step_bool = defaultdict(bool)
        for i, v in enumerate(path):
            bob_step[v] = i
            bob_step_bool[v] = True
        ans = -inf
        @cache
        def dfs2(cur, temp_path, fa, cnt):
            nonlocal ans
            v = cur
            if bob_step_bool[v] is False:
                cnt += amount[v]
            else:
                if len(temp_path) - 1 == bob_step[v]:
                    cnt += amount[v] // 2
                elif len(temp_path) - 1 > bob_step[v]:
                    cnt += 0
                else:
                    cnt += amount[v]
            if leaves_bool[cur] is True:
                #print(cur, temp_path, fa, cnt)
                ans = max(ans, cnt)
                return
            for next in g[cur]:
                if next != fa:
                    dfs2(next, tuple(list(temp_path) + [next]), cur, cnt)
        dfs2(0, tuple([0]), -1, 0)
        

        return ans
            
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

ac code（list抽离，使用回溯算法）

class Solution:
    def mostProfitablePath(self, edges: List[List[int]], bob: int, amount: List[int]) -> int:
        g = defaultdict(list)
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)
        leaves = []
        for node in g:
            if len(g[node]) == 1 and node != 0:
                leaves.append(node)
        leaves = set(leaves)
        leaves_bool = defaultdict(bool)
        for leaf in leaves:
            leaves_bool[leaf] = True
        # 先看看bob到0怎么走
        path = []
        flag = False
        temp_path = [bob]
        def dfs1(cur, fa):
            nonlocal flag, path
            if flag:
                return
            if cur == 0:
                path = temp_path[:]
                flag = True
                return
            for next in g[cur]:
                if next != fa:
                    temp_path.append(next)
                    dfs1(next, cur)
                    temp_path.pop()
        dfs1(bob, -1)
        bob_step = defaultdict(int)
        bob_step_bool = defaultdict(bool)
        for i, v in enumerate(path):
            bob_step[v] = i
            bob_step_bool[v] = True
        ans = -inf
        temp_path = [0]
        cnt = 0
        def dfs2(cur, fa):
            nonlocal ans, cnt
            cnt1 = cnt
            v = cur
            if bob_step_bool[v] is False:
                cnt1 += amount[v]
            else:
                if len(temp_path) - 1 == bob_step[v]:
                    cnt1 += amount[v] // 2
                elif len(temp_path) - 1 > bob_step[v]:
                    cnt1 += 0
                else:
                    cnt1 += amount[v]
            if leaves_bool[cur] is True:
                #print(cur, temp_path, fa, cnt)
                ans = max(ans, cnt1)
                return
            origin_cnt = cnt
            for next in g[cur]:
                if next != fa:
                    temp_path.append(next)
                    cnt = cnt1
                    dfs2(next, cur)
                    cnt = origin_cnt
                    temp_path.pop()
        dfs2(0, -1)
        

        return ans
            
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

总结

• 简单模拟dfs
• 不要用list作为py的函数参数了！
• 以后都用dfs + 回溯即可