C++ Well Commented and Explained Code
Problem Description\n\nYou are given two undirected trees with n and m nodes. The nodes have distinct labels in the ranges [0, n - 1] and [0, m - 1], respective
# Problem Description\n\nYou are given two undirected trees with `n` and `m` nodes. The nodes have distinct labels in the ranges `[0, n - 1]` and `[0, m - 1]`, respectively.\n\nYou are also provided:\n- `edges1` (a 2D integer array of size `n - 1`) which represents edges in the first tree, where `edges1[i] = [a_i, b_i]` indicates an edge between nodes `a_i` and `b_i`.\n- `edges2` (a 2D integer array of size `m - 1`) which represents edges in the second tree, where `edges2[i] = [u_i, v_i]` indicates an edge between nodes `u_i` and `v_i`.\n- An integer `k`.\n\n### Target Node\nA node `u` is **target** to node `v` if the number of edges on the path from `u` to `v` is less than or equal to `k`. Note that a node is always target to itself.\n\n### Task\nReturn an array of size `n`, where the `i-th` value is the maximum possible number of nodes **target** to node `i` of the first tree if you connect one node from the first tree to another node in the second tree.\n\n### Constraints\n- Queries are **independent**, meaning after processing each query, the added edge is removed.\n\n---\n\n## Intuition\n\n1. **DFS for Target Count**:\n   - Use a DFS to calculate the number of nodes in a tree that are within a distance of `k` edges from a given node.\n   - This gives us the count of target nodes for both trees independently.\n\n2. **Merge Trees Virtually**:\n   - For each node in the second tree, compute the maximum number of nodes target to it.\n   - Simulate adding an edge between every node of the first tree and each node of the second tree.\n   - For each query, combine the results of the two trees and return the maximum.\n\n3. **Optimization**:\n   - Precompute the DFS results for all nodes in both trees to avoid redundant calculations.\n\n---\n\n## Approach\n\n1. **Build the Adjacency List**:\n   - Represent the two trees using adjacency lists for easier traversal.\n\n2. **DFS Traversal**:\n   - Implement a helper function `dfs` to compute the number of target nodes for a given node and a specific `k`.\n\n3. **Iterate Over Nodes**:\n   - For each node in the second tree, calculate the maximum target nodes.\n   - For each node in the first tree, calculate the total target nodes by combining results from both trees.\n\n4. **Store Results**:\n   - Store the results in an array and return it.\n\n---\n\n## Complexity\n\n- **Time Complexity**:  \n  - Building adjacency lists: \\( O(n + m) \\)  \n  - DFS for all nodes in both trees: \\( O(nk + mk) \\)  \n  - Combining results: \\( O(nm) \\)  \n  **Total**: \\( O(nk + mk + nm) \\)\n\n- **Space Complexity**:  \n  - Adjacency lists: \\( O(n + m) \\)  \n  - DFS recursion stack: \\( O(k) \\)\n\n---\n\n## Code\n\n```cpp\nclass Solution {\npublic:\n    // Perform DFS to count target nodes\n    int dfs(int i, int p, vector<vector<int>> &adj, int k) {\n        if (k <= 0) return k == 0;\n        int res = 1; // Include current node\n        for (int j : adj[i]) {\n            if (j != p) {\n                res += dfs(j, i, adj, k - 1);\n            }\n        }\n        return res;\n    }\n\n    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {\n        int m = edges1.size() + 1; // Nodes in first tree\n        int n = edges2.size() + 1; // Nodes in second tree\n\n        // Build adjacency list for the first tree\n        vector<vector<int>> adj1(m);\n        for (auto &edge : edges1) {\n            adj1[edge[0]].push_back(edge[1]);\n            adj1[edge[1]].push_back(edge[0]);\n        }\n\n        // Build adjacency list for the second tree\n        vector<vector<int>> adj2(n);\n        for (auto &edge : edges2) {\n            adj2[edge[0]].push_back(edge[1]);\n            adj2[edge[1]].push_back(edge[0]);\n        }\n\n        // Precompute the maximum target nodes for each node in the second tree\n        int maxSecondTreeTargets = 0;\n        for (int i = 0; i < n; ++i) {\n            maxSecondTreeTargets = max(maxSecondTreeTargets, dfs(i, -1, adj2, k - 1));\n        }\n\n        // Compute results for each node in the first tree\n        vector<int> result(m);\n        for (int i = 0; i < m; ++i) {\n            result[i] = maxSecondTreeTargets + dfs(i, -1, adj1, k);\n        }\n\n        return result;\n    }\n};\n
['Tree', 'Depth-First Search', 'C++']