2581. Count Number of Possible Root Nodes
Description
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] = [a_{i}, b_{i}]
indicates that there is an edge between nodes a_{i}
and b_{i}
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
andv
such that there exists an edge[u, v]
in the tree.  He tells Alice that
u
is the parent ofv
in the tree.
Bob's guesses are represented by a 2D integer array guesses
where guesses[j] = [u_{j}, v_{j}]
indicates Bob guessed u_{j}
to be the parent of v_{j}
.
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 <= 10^{5}
1 <= guesses.length <= 10^{5}
0 <= a_{i}, b_{i}, u_{j}, v_{j} <= n  1
a_{i} != b_{i}
u_{j} != v_{j}
edges
represents a valid tree.guesses[j]
is an edge of the tree.guesses
is unique.0 <= k <= guesses.length
Solutions
Solution 1: Tree DP (change root)
First, we traverse the given edge set $edges$ and convert it to an adjacency list $g$ where $g[i]$ represents the adjacent nodes of node $i$. Use a hash map $gs$ to record the given guess set $guesses$.
Then, we start from node $0$ and perform a DFS to count the number of edges in $guesses$ among all the nodes that can be reached from node $0$. We use the variable $cnt$ to record this number.
Next, we start from node $0$ and perform a DFS to count the number of edges in $guesses$ in each tree with $0$ as the root. If the number is greater than or equal to $k$, it means that this node is a possible root node, and we add $1$ to the answer.
Therefore, the problem becomes to count the number of edges in $guesses$ in each tree with each node as the root. We already know that there are $cnt$ edges in $guesses$ among all the nodes that can be reached from node $0$. We can maintain this value by adding or subtracting the current edge in $guesses$ in DFS.
Assume that we are currently traversing node $i$ and $cnt$ represents the number of edges in $guesses$ with $i$ as the root node. Then, for each adjacent node $j$ of $i$, we need to calculate the number of edges in $guesses$ with $j$ as the root node. If $(i, j)$ is in $guesses$, then there is no edge $(i, j)$ in the tree with $j$ as the root node, so $cnt$ should decrease by $1$. If $(j, i)$ is in $guesses$, then there is an extra edge $(i, j)$ in the tree with $j$ as the root node, so $cnt$ should increase by $1$. That is, $f[j] = f[i] + (j, i) \in guesses  (i, j) \in guesses$. Where $f[i]$ represents the number of edges in $guesses$ with $i$ as the root node.
The time complexity is $O(n + m)$ and the space complexity is $O(n + m)$, where $n$ and $m$ are the lengths of $edges$ and $guesses$ respectively.







