are distinct.

Solution

Method 1 – Bitmask Enumeration and BFS

Intuition

Since n is small (≤ 15), we can enumerate all possible subsets of cities (using bitmasking). For each subset, if it forms a connected subtree, we can compute the maximum distance between any two cities in the subset using BFS. We count the number of subtrees for each possible maximum distance.

Approach

Build the adjacency list for the tree.
For each subset of cities (bitmask from 1 to 2^n - 1) with at least 2 cities:
- Check if the subset is connected (using BFS or DFS).
- If connected, for each node in the subset, run BFS to find the farthest node (diameter of the subtree).
- The maximum distance found is the diameter for this subset.
- Increment the count for this diameter.
Return the counts for distances from 1 to n-1.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {\n        vector<vector<int>> g(n);\n        for (auto& e : edges) {\n            g[e[0]-1].push_back(e[1]-1);\n            g[e[1]-1].push_back(e[0]-1);\n        }\n        vector<int> ans(n-1);\n        for (int mask = 1; mask < (1<<n); ++mask) {\n            if (__builtin_popcount(mask) < 2) continue;\n            vector<int> nodes;\n            for (int i = 0; i < n; ++i) if (mask & (1<<i)) nodes.push_back(i);\n            queue<int> q;\n            vector<bool> vis(n);\n            q.push(nodes[0]); vis[nodes[0]] = true;\n            int cnt = 1;\n            while (!q.empty()) {\n                int u = q.front(); q.pop();\n                for (int v : g[u]) {\n                    if ((mask & (1<<v)) && !vis[v]) {\n                        vis[v] = true; q.push(v); cnt++;\n                    }\n                }\n            }\n            if (cnt != nodes.size()) continue;\n            int diam = 0;\n            for (int u : nodes) {\n                queue<pair<int,int>> q2;\n                vector<bool> vis2(n);\n                q2.push({u, 0}); vis2[u] = true;\n                while (!q2.empty()) {\n                    auto [v, d] = q2.front(); q2.pop();\n                    diam = max(diam, d);\n                    for (int w : g[v]) {\n                        if ((mask & (1<<w)) && !vis2[w]) {\n                            vis2[w] = true; q2.push({w, d+1});\n                        }\n                    }\n                }\n            }\n            if (diam > 0) ans[diam-1]++;\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">    vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">> </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">countSubgraphsForEachDiameter</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> n</span><span style=\"color:#

Related Tags