I like to read this solution as a small machine: keep the useful information, throw away the noise. For 1617. Count Subtrees With Max Distance Between Cities, the solution in this repository is mainly a graph traversal solution.
Guide
What?
The first job is to translate the English prompt into state, transition, and stopping conditions. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: graph traversal.
The notes already sitting in the source point us in the right direction:
- enumerate all possible subtrees, check if they are valid, and calculate their maximum distances
- not sure if the "checking is a tree" part is correct or not
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are sizeOfTree, isTree, maxDist, countSubgraphsForEachDiameter, bfs.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//enumerate all possible subtrees, check if they are valid, and calculate their maximum distances
02//not sure if the "checking is a tree" part is correct or not
03//Runtime: 1572 ms, faster than 8.33% of C++ online submissions for Count Subtrees With Max Distance Between Cities.
04//Memory Usage: 132 MB, less than 8.33% of C++ online submissions for Count Subtrees With Max Distance Between Cities.
05class Solution {
06public:
07 int sizeOfTree(int subtree){
08 int size = 0;
09
10 while(subtree){
11 if(subtree & 1){
12 ++size;
13 }
14 subtree >>= 1;
15 }
16
17 return size;
18 }
19
20 bool isTree(int subtree, int& size, vector<vector<int>>& adjList, vector<int>& nodes){
21 int node = 1;
22
23 // cout << "tree: ";
24
25 while(subtree){
26 if(subtree & 1){
27 // cout << node << " ";
28 nodes.push_back(node);
29 }
30 ++node;
31 subtree >>= 1;
32 }
33 // cout << endl;
34
35 size = nodes.size();
36
37 //extra condition
38 if(size <= 1) return false;
39
40 int edgeCount = 0;
41
42 for(int i = 0; i < size; ++i){
43 for(int j = i+1; j < size; ++j){
44 auto it = find(adjList[nodes[i]].begin(), adjList[nodes[i]].end(), nodes[j]);
45 if(it == adjList[nodes[i]].end()) continue;
46 ++edgeCount;
47 }
48 }
49
50 // cout << "edgeCount: " << edgeCount << endl;
51
52 return (edgeCount == size-1);
53 }
54
55 pair<int, int> bfs(int start, vector<int>& nodes, vector<vector<int>>& adjList){
56 queue<int> q;
57 unordered_set<int> visited;
58
59 q.push(start);
60 visited.insert(start);
61
62 int dist = 0;
63 int farthestNode = -1;
64
65 while(!q.empty()){
66 int level_size = q.size();
67
68 while(level_size--){
69 int cur = q.front(); q.pop();
70 farthestNode = cur;
71
72 for(int& nei : adjList[cur]){
73 if(find(nodes.begin(), nodes.end(), nei) == nodes.end()) continue;
74 if(visited.find(nei) != visited.end()) continue;
75 visited.insert(nei);
76 q.push(nei);
77 }
78 }
79
80 ++dist;
81 }
82
83 return {dist-1, farthestNode};
84 }
85
86 int maxDist(vector<int>& nodes, vector<vector<int>>& adjList){
87 // cout << "tree: " << endl;
88 // for(int& node : nodes) cout << node << " ";
89 // cout << endl;
90
91 pair<int, int> p1 = bfs(nodes[0], nodes, adjList);
92 // cout << nodes[0] << " -> " << p1.second << " : " << p1.first << endl;
93 pair<int, int> p2 = bfs(p1.second, nodes, adjList);
94 // cout << p1.second << " -> " << p2.second << " : " << p2.first << endl;
95
96 // cout << "maxDist: " << p2.first << endl;
97 return p2.first;
98 }
99
100 vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
101 //distance from 1 to n-1
102 vector<int> ans(n-1, 0);
103
104 vector<vector<int>> adjList(n+1);
105
106 for(vector<int>& edge : edges){
107 if(edge[0] > edge[1]) swap(edge[0], edge[1]);
108 adjList[edge[0]].push_back(edge[1]);
109 adjList[edge[1]].push_back(edge[0]);
110 }
111
112 for(int subtree = 0; subtree < (1<<n); ++subtree){
113 // if(sizeOfTree(subtree) <= 1) continue;
114 // vector<int> usable;
115 int size;
116 vector<int> nodes;
117 if(!isTree(subtree, size, adjList, nodes)) continue;
118 ++ans[maxDist(nodes, adjList)-1];
119 }
120
121 return ans;
122 }
123};
124
125//enumerate all possible subtrees, check if they are valid, and calculate their maximum distances by tree diameter
126//https://leetcode.com/problems/count-subtrees-with-max-distance-between-cities/discuss/889070/Python-Bitmask-try-all-subset-of-cities-Clean-and-Concise-O(2n-*-n)
127//Runtime: 1532 ms, faster than 8.33% of C++ online submissions for Count Subtrees With Max Distance Between Cities.
128//Memory Usage: 370.5 MB, less than 8.33% of C++ online submissions for Count Subtrees With Max Distance Between Cities.
129class Solution {
130public:
131 vector<int> bfs(int src, vector<int>& nodes, vector<vector<int>>& adjList){
132 queue<int> q;
133 //index 0: dummy
134 vector<bool> visited(adjList.size(), false);
135
136 //will be the farthest point from src
137 int last = src;
138 //the distance between src and farthest point
139 int dist = 0;
140
141 q.push(src);
142 visited[src] = true;
143
144 while(!q.empty()){
145 int level_size = q.size();
146
147 while(level_size-- > 0){
148 int cur = q.front(); q.pop();
149 last = cur;
150
151 for(const int& nei : adjList[cur]){
152 //can only use edges in this subtree!!
153 if(find(nodes.begin(), nodes.end(), nei) == nodes.end()) continue;
154 if(visited[nei]) continue;
155 visited[nei] = true;
156 q.push(nei);
157 }
158 }
159
160 ++dist;
161 }
162
163 //dist is unnecessarily increased one time before exit
164 --dist;
165
166 return {static_cast<int>(count_if(visited.begin(), visited.end(),
167 [](const bool& b){return b;})),
168 last,
169 dist};
170 }
171
172 int diameterOfTree(vector<int>& nodes, vector<vector<int>>& adjList){
173 if(nodes.size() <= 1)
174 return 0;
175
176 // cout << "nodes: ";
177 // for(const int& node : nodes){
178 // cout << node << " ";
179 // }
180 // cout << endl;
181
182 vector<int> v = bfs(nodes[0], nodes, adjList);
183
184 //cannot visit all nodes, that means the tree is not connected
185 if(v[0] < nodes.size())
186 return 0;
187
188 v = bfs(v[1], nodes, adjList);
189
190 // cout << v[2] << endl;
191
192 return v[2];
193 }
194
195 int maxDistance(int state, vector<vector<int>>& adjList){
196 vector<int> nodes;
197
198 int i = 1;
199 while(state){
200 if(state & 1)
201 nodes.push_back(i);
202 state >>= 1;
203 ++i;
204 }
205
206 return diameterOfTree(nodes, adjList);
207 }
208
209 vector<int> countSubgraphsForEachDiameter(int n, vector<vector<int>>& edges) {
210 //index 0: dummy
211 vector<vector<int>> adjList(n+1);
212
213 for(const vector<int>& edge : edges){
214 adjList[edge[0]].push_back(edge[1]);
215 adjList[edge[1]].push_back(edge[0]);
216 }
217
218 vector<int> ans(n-1, 0);
219
220 for(int state = 1; state < (1<<n); ++state){
221 int md = maxDistance(state, adjList);
222 //md == 0 means cities is not a valid tree
223 if(md > 0) ++ans[md-1];
224 }
225
226 return ans;
227 }
228};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.