1617. Count Subtrees With Max Distance Between Cities.cpp
Code\n\nclass Solution {\npublic:\n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> graph(n);\n  
**Code**\n```\nclass Solution {\npublic:\n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> graph(n);\n        for (auto& e : edges) {\n            graph[e[0]-1].push_back(e[1]-1);\n            graph[e[1]-1].push_back(e[0]-1);\n        }\n        vector<int> ans(n - 1, 0);\n        for (int state = 1; state < (1 << n); state++) {\n            int d = maxDistance(state, graph, n);\n            if (d > 0) ans[d - 1] += 1;\n        }\n        return ans;\n    }    \n    int maxDistance(int state, vector<vector<int>>& graph, int n) {\n        int anyNode = 0, cntCity = 0;\n        for (int i = 0; i < n; i++) if ((state >> i) & 1) {\n            anyNode = i;\n            cntCity += 1;\n        }\n        auto [farthestNode, _, visitedSize] = bfs(anyNode, state, graph, n);\n        if (visitedSize < cntCity) return 0; \n        auto [_ig1, dist, _ig2] = bfs(farthestNode, state, graph, n);\n        return dist;\n    }    \n    tuple<int, int, int> bfs(int src, int state, vector<vector<int>>& graph, int n) {\n        unordered_set<int> visited{src};\n        queue<pair<int,int>> q;\n        q.push({src, 0});\n        int farthestNode = -1, farthestDist = 0;\n        while(!q.empty()){\n            auto [u, d] = q.front(); q.pop();\n            farthestNode = u, farthestDist = d;\n            for (int v : graph[u]){\n                if (visited.find(v) == visited.end() && (state >> v) & 1){\n                    q.push({v, d + 1});\n                    visited.insert(v);\n                }\n            }\n        }\n        return make_tuple(farthestNode, farthestDist, visited.size());\n    }\n};\n```
['C']