2652. Count Number of Possible Root Nodes
My accepted Python solution to LeetCode problem 2652, Count Number of Possible Root Nodes, running in 400ms.
- Difficulty: Hard
- Python
- Runtime 400ms
- Memory 104.6MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 400ms, memory 104.6MB, accepted 2025-12-31.
class Solution:
def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int:
from collections import defaultdict
n = len(edges) + 1
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
# Store guesses in a set for O(1) lookup
guess_set = set()
for u, v in guesses:
guess_set.add((u, v))
# First DFS: count correct guesses when 0 is root
correct_with_0 = 0
def dfs1(node, parent):
nonlocal correct_with_0
for child in graph[node]:
if child != parent:
if (node, child) in guess_set:
correct_with_0 += 1
dfs1(child, node)
dfs1(0, -1)
# Second DFS: reroot and count valid roots
result = 0
def dfs2(node, parent, correct):
nonlocal result
if correct >= k:
result += 1
for child in graph[node]:
if child != parent:
# When rerooting from node to child:
# - (node, child) becomes wrong if it was a guess
# - (child, node) becomes correct if it was a guess
new_correct = correct
if (node, child) in guess_set:
new_correct -= 1
if (child, node) in guess_set:
new_correct += 1
dfs2(child, node, new_correct)
dfs2(0, -1, correct_with_0)
return result