# [3249\. Count the Number of Good Nodes](https://leetcode.com/problems/count-the-number-of-good-nodes/)

:::spoiler Hint

:::

:::spoiler Solution

class Solution {
public:
    int countGoodNodes(vector<vector<int>>& edges)
    {
        int n = edges.size() + 1;

        vector<vector<int>> graph(n);
        for (const auto& edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        int cnt = 0;
        dfs(graph, cnt, 0, -1);
    
        return cnt;        
    }

    int dfs(vector<vector<int>>& graph, int& cnt, int node, int parent)
    {
        int totalNodes = 1;
        bool isGood = true;
        int subtreeSize = -1;

        for (int neighbor : graph[node])
        {
            if (neighbor == parent) continue;
            
            int currentSize = dfs(graph, cnt, neighbor, node);
            
            if (subtreeSize == -1)
            {
                subtreeSize = currentSize;
            }
            else if (currentSize != subtreeSize)
            {
                isGood = false;
            }
            totalNodes += currentSize;
        }

        if (isGood) cnt++;
        return totalNodes;
    }
};

- T: $O(V + E)$
- S: $O(V + E)$
:::