lc2581.统计可能的树根数目

题目链接:

题解

如果已知 fa 为根时,满足猜测的答案是 now,那么如果 nx 为根,fa 为叶子,对答案的贡献就是 (fa, nx) 和 (nx, fa)。

第一次以 0 为根,计算满足的答案,之后再 dfs,每次值影响两个节点的关系。

参考代码

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
#
# @lc app=leetcode.cn id=2581 lang=python3
#
# [2581] 统计可能的树根数目
#

# @lc code=start
class Solution:
def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int:
g = [[] for i in range(len(edges) + 1)]
for a in edges:
g[a[0]].append(a[1])
g[a[1]].append(a[0])
guesse = {(a[0], a[1]) for a in guesses}
ans = 0
base = 0
def dfs(rt, fa):

if (fa, rt) in guesse:
nonlocal base
base += 1
for nx in g[rt]:
if nx == fa:
continue
dfs(nx, rt)

dfs(0, -1)
# print(base)

def check(rt, fa, now):
nonlocal ans
if (now >= k):
ans += 1
for nx in g[rt]:
if nx == fa:
continue
tmp = now
if (rt, nx) in guesse:
tmp -= 1
if (nx, rt) in guesse:
tmp += 1
check(nx, rt, tmp)

check(0, -1, base)
return ans
# @lc code=end


lc2581.统计可能的树根数目

https://blog.xiang578.com/problem/lc2581.html

作者

Ryen Xiang

发布于

2024-02-29

更新于

2024-08-05

许可协议


网络回响

评论