Two-Way DP | O(n+m) time, O(n+m) space | C++
Intuition\nTo maximize the number of target nodes, we need to compute the number of nodes reachable from each node in the trees for a given distance k. This req
# Intuition\nTo maximize the number of target nodes, we need to compute the number of nodes reachable from each node in the trees for a given distance $$k$$. This requires efficiently combining information from both trees to calculate the contribution of each node.\n\n# Approach\n1. **Tree Representation**: Represent both trees as adjacency lists.\n2. **Target Node Calculation for $$Tree_1$$**: Perform two DFS traversals (forward and backward) to calculate the number of target nodes reachable from each node up to distance $$k$$.\n3. **Target Node Calculation for $$Tree_2$$**: Repeat the calculation for $$Tree_2$$ but for $$k\u22121$$ since we need to connect it to $$Tree_1$$.\n4. **Aggregate Results**: Use the computed results from $$Tree_2$$ to calculate the maximum additional nodes that can be reached when connecting the trees. Combine this with $$Tree_1$$\u2019s reachability to compute the final result.\n\n# Complexity\n- Time complexity: $$O(n_1 + n_2)$$\n- Space complexity: $$O(n_1 + n_2)$$\n\nwhere $$n_1$$ and $$n_2$$ are the number of nodes in $$Tree_1$$ and $$Tree_2$$, respectively. Each node and edge is visited once.\n\n# Code\n```cpp []\nclass Solution {\n    // Helper function to compute target nodes reachable from the subtree of each node\n    void forwardDFS(const vector<vector<int>> &graph, vector<vector<int>> &targets, const int &k, const int &curr, const int &prev) {\n        targets[curr][0] = 1; // Base case: current node can reach itself\n        for(const auto &next: graph[curr]) {\n            if(next == prev) {\n                continue; // Avoid revisiting the parent node\n            }\n            forwardDFS(graph, targets, k, next, curr); // Recursive DFS for children\n            for(int i = 1; i <= k; i++) {\n                targets[curr][i] += targets[next][i - 1]; // Add reachable nodes from the child\n            }\n        }\n    }\n    \n    // Helper function to compute additional target nodes considering nodes outside the subtree\n    void backwardDFS(const vector<vector<int>> &graph, vector<vector<int>> &targets, const int &k, const int &curr, const int &prev) {\n        for(const auto &next: graph[curr]) {\n            if(next == prev) {\n                continue; // Avoid revisiting the parent node\n            }\n            for(int i = k; i > 1; i--) {\n                targets[next][i] += targets[curr][i - 1] - targets[next][i - 2]; // Adjust for parent contribution\n            }\n            targets[next][1] += targets[curr][0]; // Add parent node itself\n            backwardDFS(graph, targets, k, next, curr); // Recursive DFS for children\n        }\n    }\n    \n    // Calculates the number of target nodes reachable from each node for a given k\n    vector<vector<int>> getTargetNodes(const vector<vector<int>> &graph, const int &k) {\n        const int n = graph.size();\n        vector<vector<int>> targets(n, vector<int>(k + 1, 0)); // DP table for reachable nodes\n        forwardDFS(graph, targets, k, 0, -1); // First DFS to populate targets in subtrees\n        backwardDFS(graph, targets, k, 0, -1); // Second DFS to adjust for targets outside subtree\n        return targets;\n    }\n\npublic:\n    // Main function to compute the maximum target nodes reachable after connecting two trees\n    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {\n        const int n1 = 1 + edges1.size(); // Number of nodes in first tree\n        const int n2 = 1 + edges2.size(); // Number of nodes in second tree\n        vector<int> result(n1, 1); // Default result: each node reaches itself\n        \n        if(k == 0) {\n            return result; // If k=0, no additional nodes can be reached\n        }\n\n        vector<vector<int>> graph1(n1), graph2(n2); // Graph representations for both trees\n        for(const auto &edge: edges1) {\n            graph1[edge[0]].push_back(edge[1]);\n            graph1[edge[1]].push_back(edge[0]); // Build adjacency list for tree 1\n        }\n        \n        if(k == 1) {\n            for(int i = 0; i < n1; i++) {\n                result[i] = 2 + graph1[i].size(); // Immediate neighbors and self\n            }\n            return result;\n        }\n\n        for(const auto &edge: edges2) {\n            graph2[edge[0]].push_back(edge[1]);\n            graph2[edge[1]].push_back(edge[0]); // Build adjacency list for tree 2\n        }\n\n        vector<vector<int>> targets1 = getTargetNodes(graph1, k); // Targets for tree 1\n        vector<vector<int>> targets2 = getTargetNodes(graph2, k - 1); // Targets for tree 2\n\n        int maxExtra = 0; // Max additional targets from tree 2\n        for(const auto &target: targets2) {\n            maxExtra = max(maxExtra, accumulate(target.begin(), target.end(), 0)); // Aggregate tree 2 contributions\n        }\n\n        for(int i = 0; i < n1; i++) {\n            result[i] = maxExtra + accumulate(targets1[i].begin(), targets1[i].end(), 0); // Total reachable nodes\n        }\n        return result;\n    }\n};\n\n```
['C++']