DP O(k * max(n, m))
Intuition & approach\n- While thinking solution, main trouble was whether we can avoid recomputing somehow.\n- Say we want to compute for k = 2, and we have nod
# Intuition & approach\n- While thinking solution, main trouble was whether we can avoid recomputing somehow.\n- Say we want to compute for $$k = 2$$, and we have node with index $$0$$ which is connected to node $$1$$ of the same tree i.e. we want $$DP[2][0][Answer]$$.\n- $$DP[k=2][0][Answer]$$ should be $$DP[k = 1][1][Answer]$$ but here we have also double counted edge between $$0-1$$ because $$DP[k = 1][1][Answer]$$ which be equal to count of neighbors of node $$1$$.\n- Hence, we can deduct that value which helped form $$DP[k = 1][1][Answer]$$ corresponding to node $$0$$.\n\n# Complexity\nNote: Size of looping over adjaceny matrix for a tree should be equalivalent to going over each edge where number of edges is equal to $$O(n)$$.\n- Time complexity: $$O(k * max(n, m))$$\n- Space complexity: $$O(max(n, m))$$\n\n# Code\n```cpp []\nclass Solution {\n    vector<vector<unordered_map<int, int>>> solve(int n, int k, vector<vector<int>>& adjMat) {\n        vector<vector<unordered_map<int, int>>> dp(3, vector<unordered_map<int, int>>(n));\n        for (int i = 0; i < n; i += 1) {\n            for (int j = 0; j < adjMat[i].size(); j += 1)\n                dp[0][i][adjMat[i][j]] = 0;\n            dp[0][i][-1] = 1;\n        }\n        for (int i = 0; i < n; i += 1) {\n            for (int j = 0; j < adjMat[i].size(); j += 1)\n                dp[1][i][adjMat[i][j]] = 1;\n            dp[1][i][-1] = adjMat[i].size() + 1;\n        }\n        for (int x = 2; x <= k; x += 1)\n            for (int i = 0; i < n; i += 1) {\n                dp[x % 3][i][-1] = 1;\n                for (int j = 0; j < adjMat[i].size(); j += 1) {\n                    dp[x % 3][i][adjMat[i][j]] = \n                    dp[(x - 1) % 3][adjMat[i][j]][-1] - \n                    dp[(x - 1) % 3][adjMat[i][j]][i];\n                    dp[x % 3][i][-1] += dp[x % 3][i][adjMat[i][j]];\n                }\n            }\n        return dp;\n    }\n\npublic:\n    vector<int> maxTargetNodes(\n        vector<vector<int>>& edges1,\n        vector<vector<int>>& edges2, \n        int k) {\n\n        int n = edges1.size() + 1;\n        if (k == 0) {\n            vector<int> answer(n, 1);\n            return answer;\n        }\n        \n        vector<vector<int>> adjMat1(n);\n        for (auto& edge : edges1) {\n            int a = edge[0], b = edge[1];\n            adjMat1[a].push_back(b);\n            adjMat1[b].push_back(a);\n        }\n        auto dp1 = solve(n, k, adjMat1);\n\n        if (k == 1) {\n            vector<int> answer(n);\n            for (int i = 0; i < n; i += 1)\n                answer[i] = dp1[k % 3][i][-1] + 1;\n            return answer;\n        }\n\n        int m = edges2.size() + 1;\n        vector<vector<int>> adjMat2(m);\n        for (auto& edge : edges2) {\n            int a = edge[0], b = edge[1];\n            adjMat2[a].push_back(b);\n            adjMat2[b].push_back(a);\n        }\n        auto dp2 = solve(m, k, adjMat2);\n        \n        int maxSum = 0;\n        for (int i = 0; i < m; i += 1)\n            maxSum = max(maxSum, dp2[(k - 1) % 3][i][-1]);\n\n        vector<int> answer(n);\n        for (int i = 0; i < n; i += 1)\n            answer[i] = dp1[k % 3][i][-1] + maxSum;\n        return answer;\n    }\n};\n```
['Dynamic Programming', 'C++']