C++ BFS Tree 1 and 2
Intuition\n- To connect to tree 2, there will always be one vertex that is best for everything. You can find it by using BFS on every Tree 2 vertex. $O(m^2)$\n-
# Intuition\n- To connect to tree 2, there will always be one vertex that is best for everything. You can find it by using BFS on every Tree 2 vertex. $O(m^2)$\n- Then, you need to get the **reachable count of vertices** for each vertex in Tree 1. You can find it by also using BFS on every Tree 1 vertex. $O(n^2)$\n\n# Complexity\n- Time complexity: $O(n^2+m^2)$\n\n- Space complexity: $O(n+m)$\n\n# Code\n```cpp []\n#include <bits/stdc++.h>\nusing namespace std;\n\nclass Solution {\npublic:\n    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {\n    \tint n = edges1.size() + 1, m = edges2.size() + 1;\n\n    \tif(k == 0) return vector<int>(n, 1);\t\n\n\n    \tvector<vector<int>> adj1(n), adj2(m);\n\n\t\tfor(auto& e : edges1) {\n    \t\tadj1[e[0]].push_back(e[1]);\n    \t\tadj1[e[1]].push_back(e[0]);\n    \t}\n\n    \tfor(auto& e : edges2) {\n    \t\tadj2[e[0]].push_back(e[1]);\n    \t\tadj2[e[1]].push_back(e[0]);\n    \t}\n\n    \tvector dist1(n, vector<int>(n, 0)), dist2(m, vector<int>(m, 0));\n    \tauto bfs = [&](auto& dist, auto& adj, int start) -> void {\n            vector<bool> visited(max(n, m) + 1, false);\n    \t\tdeque<int> q;\n    \t\tvisited[start] = true;\n    \t\tq.push_back(start);\n    \t\tint currDist = 0;\n    \t\twhile(!q.empty()) {\n    \t\t\tint sz = q.size();\n    \t\t\tdist[currDist] += sz;\n    \t\t\twhile(sz--) {\n    \t\t\t\tint v = q.front();\n    \t\t\t\tq.pop_front();\n    \t\t\t\tfor(int o : adj[v]) {\n                        if(!visited[o]) {\n                            visited[o] = true;\n                            q.push_back(o);\n                        }\n                    }\n    \t\t\t}\n    \t\t\t++currDist;\n    \t\t}\n    \t};\n\n    \tfor(int i = 0; i < n; i++) {\n    \t\tbfs(dist1[i], adj1, i);\n            // prefix sum so dist[i][d] = num of verts in <= d distance\n    \t\tfor(int j = 1; j < n; j++) dist1[i][j] += dist1[i][j - 1];\n    \t}\n\n    \tint best = 1;\n    \tfor(int i = 0; i < m; i++) {\n    \t\tbfs(dist2[i], adj2, i);\n            // prefix sum so dist[i][d] = num of verts in <= d distance\n    \t\tfor(int j = 1; j < m; j++) dist2[i][j] += dist2[i][j - 1];\n            // check best vert for (k - 1) [-1 because you need to travel from tree1 to tree2 first]\n    \t\tbest = max(best, dist2[i][min(k - 1, m - 1)]);\n    \t}\n\n\n    \tvector<int> res(n);\n    \tfor(int i = 0; i < n; i++) {\n    \t\tres[i] = dist1[i][min(k, n - 1)] + best;\n    \t}\n    \treturn res;\n    }\n};\n```
['C++']