1class Solution {
2    private int ans; // To count the number of good nodes
3    private List<Integer>[] graph; // To represent the graph using adjacency list
4
5    public int countGoodNodes(int[][] edges) {
6        int n = edges.length + 1; // Number of nodes is number of edges + 1
7        graph = new List[n]; // Initialize the adjacency list for the graph
8        Arrays.setAll(graph, k -> new ArrayList<>()); // Assign a new ArrayList to each node in the graph
9
10        // Build the graph from the given edges
11        for (int[] edge : edges) {
12            int a = edge[0], b = edge[1];
13            graph[a].add(b); // Add b to the adjacency list of a
14            graph[b].add(a); // Add a to the adjacency list of b
15        }
16
17        dfs(0, -1); // Start DFS from the root node 0, with a parent of -1
18        return ans; // Return the count of good nodes
19    }
20
21    private int dfs(int node, int parent) {
22        int previousChildValue = -1; // To store the value of previously visited child node
23        int subtreeNodeCount = 1; // Count the node itself
24        int isGoodNode = 1; // Initially assume the current node is a good node
25
26        // Iterate over all adjacent nodes (children)
27        for (int child : graph[node]) {
28            if (child != parent) { // Ensure that we don't revisit the parent node
29                int currentChildValue = dfs(child, node); // Perform DFS on child
30                subtreeNodeCount += currentChildValue; // Increment subtree count
31
32                // Compare subtree sizes for children to determine if it's a good node
33                if (previousChildValue < 0) {
34                    previousChildValue = currentChildValue; // Set for the first child
35                } else if (previousChildValue != currentChildValue) {
36                    isGoodNode = 0; // This node is not good if subtree sizes differ
37                }
38            }
39        }
40        ans += isGoodNode; // Increase count if it's a good node
41        return subtreeNodeCount; // Return the number of nodes in the subtree rooted at this node
42    }
43}
44

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    // Function to count good nodes in a tree represented by its edges
7    int countGoodNodes(vector<vector<int>>& edges) {
8        int n = edges.size() + 1; // Number of nodes in the graph
9        vector<int> graph[n];
10
11        // Build adjacency list representation of the graph from edge list
12        for (const auto& edge : edges) {
13            int nodeA = edge[0], nodeB = edge[1];
14            graph[nodeA].push_back(nodeB); // Add nodeB as neighbor of nodeA
15            graph[nodeB].push_back(nodeA); // Add nodeA as neighbor of nodeB for undirected graph
16        }
17
18        int goodNodesCount = 0; // Initialize count of good nodes
19        // Define a recursive lambda function for Depth First Search (DFS)
20        function<int(int, int)> dfs = [&](int current, int parent) -> int {
21            int previousSubTreeSize = -1;
22            int subTreeSize = 1;
23            bool isGoodNode = true;
24
25            // Iterate through every connected node
26            for (int neighbor : graph[current]) {
27                if (neighbor != parent) { // Ensure not to go back to parent node
28                    int currentSubTreeSize = dfs(neighbor, current);
29                    subTreeSize += currentSubTreeSize;
30
31                    // Check if previous subtree size is different
32                    if (previousSubTreeSize < 0) {
33                        previousSubTreeSize = currentSubTreeSize;
34                    } else if (previousSubTreeSize != currentSubTreeSize) {
35                        isGoodNode = false;
36                    }
37                }
38            }
39
40            goodNodesCount += isGoodNode; // Increment good node count if true
41            return subTreeSize; // Return total subtree size rooted at current node
42        };
43
44        dfs(0, -1); // Call DFS starting from node 0 with no parent
45        return goodNodesCount; // Return the count of good nodes
46    }
47};
48

1// Function to count the number of "good nodes" in a tree graph.
2function countGoodNodes(edges: number[][]): number {
3    // Calculate the number of nodes. It's one more than the number of edges, since the structure is a tree.
4    const n = edges.length + 1;
5
6    // Initialize an adjacency list to represent the graph.
7    const graph: number[][] = Array.from({ length: n }, () => []);
8
9    // Populate the graph with edges.
10    for (const [a, b] of edges) {
11        graph[a].push(b);
12        graph[b].push(a);
13    }
14
15    // Variable to keep track of the count of "good nodes".
16    let goodNodeCount = 0;
17
18    // Depth-First Search function to traverse the graph.
19    const dfs = (node: number, parent: number): number => {
20        // Initialize `pre` to -1 to track if all child nodes return the same value, `cnt` to 1 to count nodes including `node`, and `ok` to 1 assuming it's a "good node".
21        let [pre, totalNodes, isGood] = [-1, 1, 1];
22
23        // Visit adjacent nodes.
24        for (const neighbor of graph[node]) {
25            if (neighbor !== parent) {
26                // Perform DFS on the subtree rooted at this neighbor.
27                const subtreeNodeCount = dfs(neighbor, node);
28                totalNodes += subtreeNodeCount;
29
30                // Check if the "good node" condition is violated.
31                if (pre < 0) {
32                    pre = subtreeNodeCount;
33                } else if (pre !== subtreeNodeCount) {
34                    isGood = 0; // Not a "good node" if subtree sizes differ.
35                }
36            }
37        }
38
39        // Increase the global count of "good nodes" if this is a "good node".
40        goodNodeCount += isGood;
41      
42        // Return the total count of nodes in this subtree.
43        return totalNodes;
44    };
45
46    // Start DFS from node 0 (assuming node 0 is the root).
47    dfs(0, -1);
48
49    // Return the total number of "good nodes".
50    return goodNodeCount;
51}
52