What is the main pattern for solving the 'Count Number of Possible Root Nodes' problem?

The main pattern involves using array scanning along with hash lookups to efficiently count valid guesses for each potential root node.

How do hash tables help in this problem?

Hash tables allow quick lookups for each guess, significantly speeding up the process of validating potential root nodes against the guesses.

What is the time complexity of this solution?

The time complexity is `O(n + g)`, where `n` is the number of nodes and `g` is the number of guesses, due to the need to scan each node and validate guesses using hash lookups.

How does the tree structure impact the solution?

The tree structure dictates which nodes can be valid roots, as a valid root must allow for a specified number of correct parent-child guesses based on its connections.

Can this solution be applied to other tree-related problems?

Yes, the use of hash tables and array scanning for guess validation can be applied to other tree problems involving parent-child relationships or root node identification.

#2581

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计可能的树根数目

Alice 有一棵 n 个节点的树，节点编号为 0 到 n - 1 。树用一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [a i , b i ] ，表示树中节点 a i 和 b i 之间有一条边。 Alice 想要 Bob 找到这棵树的根。她允许 Bob 对这…

数组哈希表动态规划树深度优先搜索

题目描述

Alice 有一棵 n 个节点的树，节点编号为 0 到 n - 1 。树用一个长度为 n - 1 的二维整数数组 edges 表示，其中 edges[i] = [a_i, b_i] ，表示树中节点 a_i 和 b_i 之间有一条边。

Alice 想要 Bob 找到这棵树的根。她允许 Bob 对这棵树进行若干次猜测。每一次猜测，Bob 做如下事情：

选择两个 不相等 的整数 u 和 v ，且树中必须存在边 [u, v] 。
Bob 猜测树中 u 是 v 的 父节点 。

Bob 的猜测用二维整数数组 guesses 表示，其中 guesses[j] = [u_j, v_j] 表示 Bob 猜 u_j 是 v_j 的父节点。

Alice 非常懒，她不想逐个回答 Bob 的猜测，只告诉 Bob 这些猜测里面至少有 k 个猜测的结果为 true 。

给你二维整数数组 edges ，Bob 的所有猜测和整数 k ，请你返回可能成为树根的 节点数目 。如果没有这样的树，则返回 0。

示例 1：

输入：edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3
输出：3
解释：
根为节点 0 ，正确的猜测为 [1,3], [0,1], [2,4]
根为节点 1 ，正确的猜测为 [1,3], [1,0], [2,4]
根为节点 2 ，正确的猜测为 [1,3], [1,0], [2,4]
根为节点 3 ，正确的猜测为 [1,0], [2,4]
根为节点 4 ，正确的猜测为 [1,3], [1,0]
节点 0 ，1 或 2 为根时，可以得到 3 个正确的猜测。

示例 2：

输入：edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1
输出：5
解释：
根为节点 0 ，正确的猜测为 [3,4]
根为节点 1 ，正确的猜测为 [1,0], [3,4]
根为节点 2 ，正确的猜测为 [1,0], [2,1], [3,4]
根为节点 3 ，正确的猜测为 [1,0], [2,1], [3,2], [3,4]
根为节点 4 ，正确的猜测为 [1,0], [2,1], [3,2]
任何节点为根，都至少有 1 个正确的猜测。

提示：

edges.length == n - 1
2 <= n <= 10⁵
1 <= guesses.length <= 10⁵
0 <= a_i, b_i, u_j, v_j <= n - 1
a_i != b_i
u_j != v_j
edges 表示一棵有效的树。
guesses[j] 是树中的一条边。
guesses 是唯一的。
0 <= k <= guesses.length

lightbulb

解题思路

方法一：树形 DP（换根）

我们先遍历题目给定的边集合 $edges$ ，将其转换为邻接表 $g$ ，其中 $g[i]$ 表示节点 $i$ 的所有邻接节点。用哈希表 $gs$ 记录题目给定的猜测集合 $guesses$ 。

接下来，我们先从节点 $0$ 开始，进行一次 DFS，统计从节点 $0$ 出发，能够到达的所有节点中，有多少条边在 $guesses$ 中。我们用变量 $cnt$ 记录这个数量。

然后，我们再从节点 $0$ 开始，进行一次 DFS，统计以每个点为根的树中，有多少条边在 $guesses$ 中。如果这个数量大于等于 $k$ ，则说明该节点是一个可能的根节点，我们将答案加 $1$ 。

因此，问题就转化为了求以每个点为根的树中，有多少条边在 $guesses$ 中。我们已经知道了从节点 $0$ 出发，能够到达的所有节点中，有多少条边在 $guesses$ 中，即 $cnt$ 。我们可以通过在 DFS 中，将 $cnt$ 的值加上或减去当前边是否在 $guesses$ 中，来维护这个值。

假设我们当前遍历到节点 $i$ ，此时 $cnt$ 表示以 $i$ 为根节点，有多少条边在 $guesses$ 中。那么对于 $i$ 的每个邻接节点 $j$ ，我们要计算以 $j$ 为根节点，有多少条边在 $guesses$ 中。如果 $(i, j)$ 在 $guesses$ 中，那么以 $j$ 为根节点的，就不存在 $(i, j)$ 这条边，因此 $cnt$ 的值要减去 $1$ 。如果 $(j, i)$ 在 $guesses$ 中，那么以 $j$ 为根节点的，要多出一条 $(i, j)$ 这条边，因此 $cnt$ 的值要加上 $1$ 。即 $f[j] = f[i] + (j, i) \in guesses - (i, j) \in guesses$ 。其中 $f[i]$ 表示以 $i$ 为根节点，有多少条边在 $guesses$ 中。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n + m)$ 。其中 $n$ 和 $m$ 分别为 $edges$ 和 $guesses$ 的长度。

相似题目：

834. 树中距离之和

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

class Solution:
    def rootCount(
        self, edges: List[List[int]], guesses: List[List[int]], k: int
    ) -> int:
        def dfs1(i, fa):
            nonlocal cnt
            for j in g[i]:
                if j != fa:
                    cnt += gs[(i, j)]
                    dfs1(j, i)

        def dfs2(i, fa):
            nonlocal ans, cnt
            ans += cnt >= k
            for j in g[i]:
                if j != fa:
                    cnt -= gs[(i, j)]
                    cnt += gs[(j, i)]
                    dfs2(j, i)
                    cnt -= gs[(j, i)]
                    cnt += gs[(i, j)]

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
        gs = Counter((u, v) for u, v in guesses)
        cnt = 0
        dfs1(0, -1)
        ans = 0
        dfs2(0, -1)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate recognize that hash table lookups can optimize the guess validation step?
question_mark
Can the candidate discuss how to efficiently check multiple nodes while avoiding redundant calculations?
question_mark
Is the candidate aware of the computational limits with respect to the input size, particularly in terms of time and space complexity?

warning

常见陷阱

外企场景

error
Failing to efficiently count correct guesses for each root node, leading to poor performance with large input sizes.
error
Overcomplicating the problem by ignoring the potential for hashing and array scanning to simplify the solution.
error
Not considering the impact of tree structure on the possible root candidates and incorrectly assuming multiple valid roots without checking all conditions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to check for a higher number of correct guesses, requiring adjustments to the threshold `k`.
arrow_right_alt
Introduce additional constraints such as limiting the number of guesses Bob can make, altering the complexity and optimization needs.
arrow_right_alt
Test with larger trees and ensure that performance scales well for up to `n = 105` and `g = 105`.

help

常见问题

外企场景

继续练习

#2646 最小化旅行的价格总和 #2368 受限条件下可到达节点的数目 #1993 树上的操作