Tap here to switch tabs
Problem
Submissions

Problem: Count Number of Possible Root Nodes

Try to solve the Count Number of Possible Root Nodes problem.

Statement

An undirected tree with nn nodes labeled from 00 to n−1n - 1 is given as a 22D integer array edges of length n−1n - 1, where edges[i] =[ai,bi]= [a_i, b_i] indicates an undirected edge between node aia_i and node bib_i.

You are also given a 22D integer array guesses, where guesses[j] =[uj,vj]= [u_j, v_j] represents a guess that node uju_j is the parent of node vjv_j, and an integer k.

When a node is chosen as the root of the tree, every edge in the tree becomes directed away from that root. A guess guesses[j] =[uj,vj]= [u_j, v_j] is considered correct if node uju_j is the direct parent of node vjv_j in the resulting rooted tree.

Return the total number of possible root nodes that result in at least k correct guesses.

Constraints:

  • edges.length =n−1= n - 1

  • 2≤n≤1052 \leq n \leq 10^5

  • 1≤1 \leq guesses.length ≤105\leq 10^5

  • 0≤ai,bi,uj,vj≤n−10 \leq a_i, b_i, u_j, v_j \leq n - 1

  • ai≠bia_i \neq b_i

  • uj≠vju_j \neq v_j

  • edges represents a valid tree.

  • guesses[j] is an edge of the tree.

  • guesses contains unique elements.

  • 0≤0 \leq k ≤\leq guesses.length

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count Number of Possible Root Nodes

Try to solve the Count Number of Possible Root Nodes problem.

Statement

An undirected tree with nn nodes labeled from 00 to n−1n - 1 is given as a 22D integer array edges of length n−1n - 1, where edges[i] =[ai,bi]= [a_i, b_i] indicates an undirected edge between node aia_i and node bib_i.

You are also given a 22D integer array guesses, where guesses[j] =[uj,vj]= [u_j, v_j] represents a guess that node uju_j is the parent of node vjv_j, and an integer k.

When a node is chosen as the root of the tree, every edge in the tree becomes directed away from that root. A guess guesses[j] =[uj,vj]= [u_j, v_j] is considered correct if node uju_j is the direct parent of node vjv_j in the resulting rooted tree.

Return the total number of possible root nodes that result in at least k correct guesses.

Constraints:

  • edges.length =n−1= n - 1

  • 2≤n≤1052 \leq n \leq 10^5

  • 1≤1 \leq guesses.length ≤105\leq 10^5

  • 0≤ai,bi,uj,vj≤n−10 \leq a_i, b_i, u_j, v_j \leq n - 1

  • ai≠bia_i \neq b_i

  • uj≠vju_j \neq v_j

  • edges represents a valid tree.

  • guesses[j] is an edge of the tree.

  • guesses contains unique elements.

  • 0≤0 \leq k ≤\leq guesses.length