O((N + M) * K) Tree DP using a Single DFS on Each Tree | Detailed Explanation & Comments
Intuition\n- We can arbitrarily root each tree at a vertex (0 in accompanying code), then perform DFS on this root.\n- Tree structure: By rooting the tree and p
# Intuition\n- We can **arbitrarily root each tree** at a vertex (`0` in accompanying code), then **perform DFS on this root**.\n- **Tree structure**: By rooting the tree and performing DFS traversal on the root, each node in the tree will have a single parent (except the root), and optionally some children.\n- Observe that paths of length `d` from a vertex `v` can go in 1 of 2 directions: either i) **forward** down to `v`\'s descendants, or ii) **backward** up to `v`\'s parent.\n- We can accurately **calculate the number of forward paths during DFS**. **Every** forward path of length `d` from `v` contributes **one** corresponding forward path of length `d + 1` to `v`\u2019s parent. Recurrence relation, for any distance `d`:\n$$\\text{fwd\\_paths}[v][d] = \\sum_{\\text{child } u \\text{ of } v} \\text{fwd\\_paths}[u][d - 1]$$.\n- Determination of the number of **backward paths** requires that we process each node **in topological order**, such that all paths, in any directions, of any distance from a parent node must have been calculated before we can process its children.\n- For a vertex `v` with parent `p`, a **backward** path of length `d` can take 1 of 2 directions:\n    - i) The path starts from `v`, passes through `p` then goes **forward** (relative to `p`) through another child of `p` and ending in some descendants of `p` .\n    - ii) The path also starts from `v` and passes through `p` but continues to move **backward** (relative to `p`) through `p`\'s parent.\n- The **first type of backward paths** from `v` with length `d` ends up going **forward** from `p` .\n    - So the length of the segment from `p` of such paths will be `d - 1` to account for the edge `(v, p)`. There are $\\text{fwd\\_paths}[p][d-1]$ such paths.\n    - However, note that these also include paths that go through `v` which we do not want (i.e. we only want paths that, after starting from `v` and passing `p`, will cross some other children of `p`). There are $\\text{fwd\\_paths}[v][d-2]$ paths that start from `p` and passes through `v` with length `d - 1`, so we can subtract these from our calculation.\n    - Thus, the recurrence relation for these paths is:\n$$\\text{bckwd\\_paths\\_type\\_i}[v][d]=\\text{fwd\\_paths}[p][d-1] - \\text{fwd\\_paths}[v][d-2]$$.\n- The **second type of backward paths** from `v` with length `d` goes backward from `p`. Again, the length of the segment from `p` of such paths is `d - 1`. So the recurrence relation for these paths is:\n$$\\text{bckwd\\_paths\\_type\\_ii}[v][d] = \\text{bckwd\\_paths}[p][d-1]$$.\n- The **total number of backward paths** from `v` with a particular length `d` is just the sum of the aforementioned two sub-types. So, in summary:\n$$\\text{bckwd\\_paths}[v][d] = \\text{fwd\\_paths}[p][d-1]-\\text{fwd\\_paths}[v][d-2] + \\text{bckwd\\_paths}[p][d-1]$$.\n- Thus, for any node `v` in either tree, before joining them, the total number of paths of length **at most** `k` is just the **sum of both forward and backward paths** from `v` with lengths **at most** `k`: (note that we don\u2019t count backward paths of length `0` to avoid double-counting paths of length `0`):\n$$\\text{count}[v]_k=\\sum_{d_1=0}^{k}\\text{fwd\\_paths}[v][d_1] + \\sum_{d_2=1}^{k}\\text{bckwd\\_paths}[v][d_2]$$.\n- Back to our original problem, to **maximize** the number of nodes with distance `<= k` to any node `v` from the first tree, we want to connect `v` of the first tree with a node `u` in the second tree such that `u` has the **maximum** number of nodes with distance `<= k - 1` from `u`  (subtract `1` to account for the node `(u, v)`).\nSo, if we define `maxConnection` as the max number of nodes with distance `<= k - 1`  from any node in the second tree: $\\text{maxConnection} = \\text{max}_{u \\in V_2}(\\text{count2}[u]_{k-1})$, then for any vertex `v` in the first tree, the answer after joining the two trees would be:\n$$\\text{count1}[v]_{k, {\\text{ after\\_join}}} = \\text{count1}[v]_{k, {\\text{ before\\_join}}} + \\text{maxConnection } (\\forall v \\in V_1)$$.\n\n# Approach\n- **Edge case** of `k = 0`: return an array of all `1`\'s.\n- Build the **adjacency lists** for both trees and store in `tree1` and `tree2`.\n- **Perform DFS** on each tree to calculate **forward paths**:\n    - Use a pre-order queue (or post-order stack) to keep track of topological order.\n    - Store the parent `p` of this node `v` in a `parent` array such that `parent[v] = p`.\n    - Store the number of **forward** paths with length `d` from vertex `v` in `dp[v][d]` :\n        - Base case (at start of DFS): `dp[v][0] = 1` because there is exactly 1 node of distance 0 from `v` (itself).\n        - (At end of DFS) For each distance `d = 1` through `d = k`, merge the current node\u2019s contribution to its parent\u2019s number of forward paths: `dp[p][d] += dp[v][d - 1]`.\n- Traverse each node in each tree in topological order to calculate **backward** **paths** and **total**  number of paths using **DP**.\n    - Store the number of backward paths with length `d` from vertex `v` in `backtrack[v][d]`, and the total number of paths (both forward and backward) with length **at most** `k` (or `k - 1` for the second tree) from vertex `v` in `count[v]`.\n    - If `v` is not the root, then `backtrack[v][1] = 1` (there is 1 backward path of length 1, which is the path back to `v`\'s parent `p`).\n    - If `v` is not the root, then for any distance `1 < d <= k` (or `<= k - 1` for the second tree) , the number of backward paths from node `v` with parent `p` is `backtrack[v][d] = dp[p][d - 1] - dp[v][d - 2] + backtrack[p][d - 1]`.\n    - **Sum all forward and backward paths** and store in `count[v]`.\n- Iterate through all the values in `count2` (the `count` array associated with the second tree) to find the `maxConnectivity`.\n- Iterate through all the values in `count1` (the `count` array associated with the first tree) and add `maxConnectivity` to each, which yields the desired result.\n- Return `count1` .\n# Complexity\n- Time complexity: $$\\text{O}((N + M) \\cdot K)$$\n- Space complexity: $$\\text{O}((N + M) \\cdot K)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    \n    public int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {\n        final int N = edges1.length + 1;\n        final int M = edges2.length + 1;\n\n        if (k == 0) {\n            int[] res = new int[N];\n            Arrays.fill(res, 1);\n            return res;\n        }\n\n        // build adjacency lists\n        List<Integer>[] tree1 = buildAdj(edges1, N);\n        List<Integer>[] tree2 = buildAdj(edges2, M);\n\n        // dp1[v][d] stores number of descendants of v in tree1 at distance d from v (forward paths)\n        // dp2[v][d] stores number of descendants of v in tree2 at distance d from v (forward paths)\n        int[][] dp1 = new int[N][k + 1]; // distance ranging 0 to k\n        int[][] dp2 = new int[M][k]; // distance ranging 0 to (k - 1)\n        int[] parent1 = new int[N];\n        int[] parent2 = new int[M];\n        Queue<Integer> q1 = new LinkedList<>();\n        Queue<Integer> q2 = new LinkedList<>();\n\n        dfs(0, -1, tree1, parent1, dp1, q1, k); // root tree1 arbitrarily at node 0\n        dfs(0, -1, tree2, parent2, dp2, q2, k - 1); // root tree2 arbitrarily at node 0\n        // only interested in paths of length up to k - 1 in tree2 to account for 1 edge\n        // connecting the 2 trees\n\n        // backtrack1[v][d] stores number of paths in tree1 of length d that start from v and\n        // passes through the parent of v (backward paths)\n        int[][] backtrack1 = new int[N][k + 1]; // distance ranging 0 to k\n        int[][] backtrack2 = new int[M][k]; // distance ranging 0 to (k - 1)\n        int[] count1 = new int[N]; // store all paths of lengths <= k in tree1 that start from v in any direction\n        int[] count2 = new int[M]; // store all paths of lengths <= k - 1 in tree2 that start from v in any direction\n\n        // populate the backtrack and count arrays\n        calcBacktrack(q1, parent1, dp1, backtrack1, count1, k);\n        calcBacktrack(q2, parent2, dp2, backtrack2, count2, k - 1);\n\n        int maxConnectivity = 1;\n        for (int count : count2)\n            maxConnectivity = Math.max(maxConnectivity, count);\n        \n        // overwrite answer onto count1\n        for (int v = 0; v < N; v++)\n            count1[v] += maxConnectivity;\n        \n        return count1;\n    }\n\n    private List<Integer>[] buildAdj(int[][] edges, int vertexCount) {\n        List<Integer>[] tree = new List[vertexCount];\n        int u, v;\n        for (int[] edge : edges) {\n            u = edge[0];\n            v = edge[1];\n            if (tree[u] == null) tree[u] = new LinkedList<Integer>();\n            if (tree[v] == null) tree[v] = new LinkedList<Integer>();\n            tree[u].add(v);\n            tree[v].add(u);\n        }\n        return tree;\n    }\n\n    private void dfs(int v, int p, List<Integer>[] adj, int[] parent, int[][] dp, Queue<Integer> q, int k) {\n        dp[v][0] = 1; // distance of 0\n        q.offer(v); // pre-order queue\n        parent[v] = p; // mark p as the parent of v\n\n        if (adj[v] != null)\n            for (int u : adj[v]) {\n                if (u == p) continue;\n                dfs(u, v, adj, parent, dp, q, k);\n            }\n\n        // at this point all children nodes have been processed\n        if (p == -1) // if this is the root node\n            return;\n        \n        // merge current node\'s contributions to its parent\n        for (int d = 1; d <= k; d++)\n            dp[p][d] += dp[v][d - 1]; \n    }\n\n    private void calcBacktrack(Queue<Integer> q, int[] parent, int[][] dp, int[][] backtrack, int[] count, int k) {\n        int v, p;\n\n        // populating the backtrack matrix requires processing nodes in topological order\n        // so that data for a parent is fully computed by the time start processing child\n        // can use either a preorder queue like here, or postorder stack\n        while (!q.isEmpty()) {\n            v = q.poll();\n            p = parent[v];\n            \n            // distance 0 from v\n            count[v] = dp[v][0];\n\n            // distance 1 from v\n            if (k >= 1) {\n                if (p != -1) // cannot backtrack if v is the root node\n                    backtrack[v][1] = 1;\n                // from v to descendants, and from v back through parent of v\n                count[v] += dp[v][1] + backtrack[v][1];\n            }\n\n            // distances 1 < d <= k from v\n            for (int d = 2; d <= k; d++) {\n                if (p != -1) // cannot backtrack if v is the root node\n                    \n                    // paths of distance d from v, that goes from v back to the parent of v (p)\n                    // then either go through another child of p, or back to grandparent\n                    \n                    // paths from p will have length d - 1 to account for edge (p-v)\n                    \n                    // when using dp[p][d - 1] this number also includes forward paths that\n                    // go through v which we don\'t want, so we have to subtract these sub-paths\n                    backtrack[v][d] = dp[p][d - 1] - dp[v][d - 2] + backtrack[p][d - 1];\n\n                // from v to descendants, and from v back through parent of v\n                count[v] += dp[v][d] + backtrack[v][d];\n            }\n        }\n    }\n}\n```
['Dynamic Programming', 'Depth-First Search', 'Java']