统计可能的树根数目

难度: Hard

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

Submission

运行时间: 251 ms

内存: 67.9 MB

class Solution:
    def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int:
        n=len(edges)+1
        m=len(guesses)
        tree=list(range(n))
        way=[[]for i in range(n)]
        for i,j in edges:
            way[i].append(j)
            way[j].append(i)

        st=[(0,-1)]
        while st:
            x,y=st.pop()
            for i in way[x]:
                if i!=y:
                    tree[i]=x
                    st.append((i,x))

        t=0
        f=[0]*n
        for i,j in guesses:
            if tree[j]==i:
                f[j]+=1
            else:
                f[i]-=1
                t+=1

        st=[0]
        while st:
            x=st.pop()
            for i in way[x]:
                if i!=tree[x]:
                    f[i]+=f[x]
                    st.append(i)

        ans=0
        for i in f:
            if i<=m-t-k:
                ans+=1
        return (ans)

Explain

此题解采用了基于DFS遍历和动态计数的方法。首先，它通过DFS从一个固定的节点（节点0）出发，为树中的每个节点建立其父节点的映射关系。然后，使用这个映射关系来判断Bob的每次猜测是否正确。对于每个猜测，如果猜对了（即当前的父子关系符合猜测），对应的节点的正确猜测数增加；如果猜错，则对应节点的错误猜测数增加，并将总的错误数加1。接着，再次使用DFS来从根节点开始传播这些猜测的统计结果到所有节点，以此来计算每个节点作为树根时，正确猜测的总数。最后，根据每个节点的猜测统计结果，计算出能成为树根的节点数量，即那些符合条件（至少k个正确猜测）的节点。

时间复杂度: O(n + m)

空间复杂度: O(n)

class Solution:
    def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int:
        n = len(edges) + 1  # 树中节点的总数
        m = len(guesses)  # 总猜测次数
        tree = list(range(n))  # 初始化每个节点的父节点为其自身
        way = [[] for i in range(n)]  # 邻接列表
        for i, j in edges:  # 构建无向图的邻接列表
            way[i].append(j)
            way[j].append(i)

        # DFS遍历树以建立每个节点的父节点关系
        st = [(0, -1)]  # 初始节点为0，父节点为-1
        while st:
            x, y = st.pop()
            for i in way[x]:
                if i != y:
                    tree[i] = x
                    st.append((i, x))

        t = 0  # 统计错误的猜测次数
        f = [0] * n  # 统计每个节点作为根时，符合的猜测次数
        for i, j in guesses:
            if tree[j] == i:  # 如果猜测正确
                f[j] += 1
            else:  # 如果猜测错误
                f[i] -= 1
                t += 1

        # 再次DFS遍历，累计每个节点的猜测统计信息
        st = [0]  # 从根节点开始
        while st:
            x = st.pop()
            for i in way[x]:
                if i != tree[x]:
                    f[i] += f[x]
                    st.append(i)

        ans = 0  # 计算可能的根节点数量
        for i in f:
            if i <= m - t - k:  # 如果该节点的正确猜测数满足条件
                ans += 1
        return ans

Explore

在树结构中，DFS和BFS都是有效的遍历方式，它们都可以用来建立父节点映射关系。选择DFS而不是BFS的原因可能是出于简化实现的考虑，因为DFS通常使用递归或者栈实现，代码较为简洁。在树这种没有环的图结构中，DFS能够确保每个节点访问一次，且在访问子节点前就完成了父节点到当前节点的映射，这样的顺序对于建立父节点映射是十分方便的。而BFS虽然也可以完成相同的任务，但在实现上需要使用队列，并且在每一层的节点都被同时处理，这在某些情况下可能会略显复杂。因此，在没有特别需求的情况下，选择DFS是一种简便的策略。

在处理猜测时，如果猜测错误（即猜测的父子关系不符合实际的父子关系），对应节点的统计值减一是因为这种猜测对于该节点成为根节点是不利的。错误猜测反映了当前节点与其子节点之间关系的误解，如果一个节点有较多错误猜测，表明它作为根节点时，构建的树与实际的父子关系较为不符，因此这种处理可以帮助减少这些节点作为候选根节点的可能性。这种处理方式确保了只有当节点与其子节点的关系较为准确时，该节点作为根的可能性才会增加，从而帮助筛选出更可能的根节点候选。

在题解中，第二次DFS遍历用于从根节点开始，将每个节点的猜测统计信息传播给其子节点。具体来说，每个节点会将自己的猜测统计值（包括正确和错误的猜测数）累加到其所有直接子节点的统计值中。这种传播逻辑确保了父节点的猜测结果会影响到所有的子节点，使得每个节点的统计值在遍历结束时反映了从根到该节点路径上所有猜测的综合结果。通过这种方式，可以计算出每个节点作为树根时的总猜测正确数，进一步用于判断哪些节点满足成为树根的条件。