Tap here to switch tabs
Problem
Submissions

Problem: Count the Number of Good Nodes

Try to solve the Count the Number of Good Nodes problem.

Statement

There is an undirected tree with nn nodes labeled from 00 to n−1n - 1, rooted at node 00. You are given a 2extD2 ext{D} integer array edges of length n−1n - 1, where edges[i] =[ai,bi]= [a_i, b_i] indicates that there is an edge between nodes aia_i and bib_i in the tree.

A node is considered good if all subtrees rooted at its children have the exact same size.

Return the total number of good nodes in the given tree.

Note: A subtree of a node includes that child node and all of its descendants. Any leaf node is also considered a good node since it has 00 children.

Constraints:

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

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

  • edges[i].length =2= 2

  • 0≤ai,bi<n0 \leq a_i, b_i < n

  • The input is generated such that edges represents a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Count the Number of Good Nodes

Try to solve the Count the Number of Good Nodes problem.

Statement

There is an undirected tree with nn nodes labeled from 00 to n−1n - 1, rooted at node 00. You are given a 2extD2 ext{D} integer array edges of length n−1n - 1, where edges[i] =[ai,bi]= [a_i, b_i] indicates that there is an edge between nodes aia_i and bib_i in the tree.

A node is considered good if all subtrees rooted at its children have the exact same size.

Return the total number of good nodes in the given tree.

Note: A subtree of a node includes that child node and all of its descendants. Any leaf node is also considered a good node since it has 00 children.

Constraints:

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

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

  • edges[i].length =2= 2

  • 0≤ai,bi<n0 \leq a_i, b_i < n

  • The input is generated such that edges represents a valid tree.