统计可能的树根数目

Alice has an undirected tree with n nodes labeled from 0 to n - 1. The tree is represented as a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

Alice wants Bob to find the root of the tree. She allows Bob to make several guesses about her tree. In one guess, he does the following:

• Chooses two distinct integers u and v such that there exists an edge [u, v] in the tree.
• He tells Alice that u is the parent of v in the tree.

Bob's guesses are represented by a 2D integer array guesses where guesses[j] = [uj, vj] indicates Bob guessed uj to be the parent of vj.

Alice being lazy, does not reply to each of Bob's guesses, but just says that at least k of his guesses are true.

Given the 2D integer arrays edges, guesses and the integer k, return the number of possible nodes that can be the root of Alice's tree. If there is no such tree, return 0.

 

Example 1:

Input: edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3
Output: 3
Explanation: 
Root = 0, correct guesses = [1,3], [0,1], [2,4]
Root = 1, correct guesses = [1,3], [1,0], [2,4]
Root = 2, correct guesses = [1,3], [1,0], [2,4]
Root = 3, correct guesses = [1,0], [2,4]
Root = 4, correct guesses = [1,3], [1,0]
Considering 0, 1, or 2 as root node leads to 3 correct guesses.

Example 2:

Input: edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1
Output: 5
Explanation: 
Root = 0, correct guesses = [3,4]
Root = 1, correct guesses = [1,0], [3,4]
Root = 2, correct guesses = [1,0], [2,1], [3,4]
Root = 3, correct guesses = [1,0], [2,1], [3,2], [3,4]
Root = 4, correct guesses = [1,0], [2,1], [3,2]
Considering any node as root will give at least 1 correct guess. 

 

Constraints:

• edges.length == n - 1
• 2 <= n <= 105
• 1 <= guesses.length <= 105
• 0 <= ai, bi, uj, vj <= n - 1
• ai != bi
• uj != vj
• edges represents a valid tree.
• guesses[j] is an edge of the tree.
• guesses is unique.
• 0 <= k <= guesses.length

/*
 * 思路：
 * 1. 构建树的邻接表表示。
 * 2. 使用DFS遍历树，找出每个节点作为根时的父子关系。
 * 3. 使用Java Stream API计算每个节点作为根时正确的猜测数量。
 * 4. 如果正确的猜测数量不小于k，则该节点可能成为树的根。
 */
import java.util.*;
import java.util.stream.*;

public class Solution {
    public int rootCount(int[][] edges, int[][] guesses, int k) {
        int n = edges.length + 1;
        List<Integer>[] tree = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            tree[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            tree[edge[0]].add(edge[1]);
            tree[edge[1]].add(edge[0]);
        }
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        dfs(tree, parent, 0, -1);
        return (int) IntStream.range(0, n)
            .filter(i -> countCorrectGuesses(parent, guesses, i) >= k)
            .count();
    }

    private void dfs(List<Integer>[] tree, int[] parent, int node, int par) {
        parent[node] = par;
        for (int neighbor : tree[node]) {
            if (neighbor != par) {
                dfs(tree, parent, neighbor, node);
            }
        }
    }

    private long countCorrectGuesses(int[] parent, int[][] guesses, int root) {
        return Arrays.stream(guesses)
            .filter(guess -> parent[guess[1]] == guess[0])
            .count();
    }
}

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

O(n + m)

O(n)