# Maximize the Number of Target Nodes After Connecting Trees II
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximize-the-number-of-target-nodes-after-connecting-trees-ii)
Canonical: https://scaleengineer.com/dsa/problems/maximize-the-number-of-target-nodes-after-connecting-trees-ii
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree
**Companies:** [jio](https://scaleengineer.com/companies/jio)
---
## Problem
There exist two **undirected** trees with `n` and `m` nodes, labeled from `[0, n - 1]` and `[0, m - 1]`, respectively.

You are given two 2D integer arrays `edges1` and `edges2` of lengths `n - 1` and `m - 1`, respectively, where `edges1[i] = [ai, bi]` indicates that there is an edge between nodes `ai` and `bi` in the first tree and `edges2[i] = [ui, vi]` indicates that there is an edge between nodes `ui` and `vi` in the second tree.

Node `u` is **target** to node `v` if the number of edges on the path from `u` to `v` is even. **Note** that a node is _always_ **target** to itself.

Return an array of `n` integers `answer`, where `answer[i]` is the **maximum** possible number of nodes that are **target** to node `i` of the first tree if you had to connect one node from the first tree to another node in the second tree.

**Note** that queries are independent from each other. That is, for every query you will remove the added edge before proceeding to the next query.

**Example 1:**

**Input:** edges1 = \[\[0,1\],\[0,2\],\[2,3\],\[2,4\]\], edges2 = \[\[0,1\],\[0,2\],\[0,3\],\[2,7\],\[1,4\],\[4,5\],\[4,6\]\]

**Output:** \[8,7,7,8,8\]

**Explanation:**

* For `i = 0`, connect node 0 from the first tree to node 0 from the second tree.
* For `i = 1`, connect node 1 from the first tree to node 4 from the second tree.
* For `i = 2`, connect node 2 from the first tree to node 7 from the second tree.
* For `i = 3`, connect node 3 from the first tree to node 0 from the second tree.
* For `i = 4`, connect node 4 from the first tree to node 4 from the second tree.
![](https://assets.glich.co/dsa/maximize-the-number-of-target-nodes-after-connecting-trees-ii/image0.png)

**Example 2:**

**Input:** edges1 = \[\[0,1\],\[0,2\],\[0,3\],\[0,4\]\], edges2 = \[\[0,1\],\[1,2\],\[2,3\]\]

**Output:** \[3,6,6,6,6\]

**Explanation:**

For every `i`, connect node `i` of the first tree with any node of the second tree.

![](https://assets.glich.co/dsa/maximize-the-number-of-target-nodes-after-connecting-trees-ii/image1.png)

**Constraints:**

* `2 <= n, m <= 105`
* `edges1.length == n - 1`
* `edges2.length == m - 1`
* `edges1[i].length == edges2[i].length == 2`
* `edges1[i] = [ai, bi]`
* `0 <= ai, bi < n`
* `edges2[i] = [ui, vi]`
* `0 <= ui, vi < m`
* The input is generated such that `edges1` and `edges2` represent valid trees.

# Approaches
## Naive Brute-Force Simulation
This approach directly simulates the process described in the problem. For each query node `i` in the first tree, we exhaustively check every possible pair of nodes `(u, v)` (one from each tree) to form a connection. For each such connection, we calculate the total number of nodes that become target to `i` by finding path lengths in the newly formed combined tree. We keep track of the maximum number of targets found across all possible connections for each `i`.
**Time:** O(n * n * m * (n + m)). For each of the `n` queries, we loop `n*m` times. Inside, we run two BFS traversals taking O(n) and O(m). This is prohibitively slow. · **Space:** O(n + m) to store adjacency lists and data for BFS.
**Pros:** Simple to understand as it directly follows the problem statement.
**Cons:** Extremely inefficient and will time out for the given constraints.; Performs a large amount of redundant computation.
### Explanation
The algorithm iterates through all `n` choices for the query node `i`. For each `i`, it then iterates through all `n` choices for the connection node `u` in Tree1 and all `m` choices for the connection node `v` in Tree2. Inside the innermost loop, it calculates the number of target nodes. This involves computing distances from `i` in Tree1 (via one BFS) and from `v` in Tree2 (via another BFS). This process is repeated for every single combination, leading to a very high time complexity.

```java
// This is a conceptual representation of the brute-force logic.
// A literal implementation would be too complex and inefficient to be practical.
class Solution {
    // Helper to run BFS and get distances from a start node in a given tree
    private int[] bfs(int startNode, int numNodes, List<List<Integer>> adj) {
        int[] dist = new int[numNodes];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();

        dist[startNode] = 0;
        q.offer(startNode);

        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.offer(v);
                }
            }
        }
        return dist;
    }

    public int[] maximizeTargetNodes(int n, int[][] edges1, int m, int[][] edges2) {
        List<List<Integer>> adj1 = new ArrayList<>();
        for (int i = 0; i < n; i++) adj1.add(new ArrayList<>());
        for (int[] edge : edges1) {
            adj1.get(edge[0]).add(edge[1]);
            adj1.get(edge[1]).add(edge[0]);
        }

        List<List<Integer>> adj2 = new ArrayList<>();
        for (int i = 0; i < m; i++) adj2.add(new ArrayList<>());
        for (int[] edge : edges2) {
            adj2.get(edge[0]).add(edge[1]);
            adj2.get(edge[1]).add(edge[0]);
        }

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            long maxTargets = 0;
            int[] distsFromI = bfs(i, n, adj1);

            for (int u = 0; u < n; u++) {
                for (int v = 0; v < m; v++) {
                    long currentTargets = 0;
                    // Targets in Tree1
                    for (int j = 0; j < n; j++) {
                        if (distsFromI[j] % 2 == 0) {
                            currentTargets++;
                        }
                    }

                    // Targets in Tree2
                    int[] distsFromV = bfs(v, m, adj2);
                    int dist_i_u = distsFromI[u];

                    for (int k = 0; k < m; k++) {
                        if ((dist_i_u + 1 + distsFromV[k]) % 2 == 0) {
                            currentTargets++;
                        }
                    }
                    maxTargets = Math.max(maxTargets, currentTargets);
                }
            }
            answer[i] = (int) maxTargets;
        }
        return answer;
    }
}
```
### Algorithm
- For each query node `i` in the first tree (from `0` to `n-1`):
  - Initialize a variable `max_targets_for_i` to 0.
  - Iterate through every possible node `u` in the first tree to connect from.
  - Iterate through every possible node `v` in the second tree to connect to.
    - For this specific connection `(u, v)`, calculate the total number of target nodes with respect to `i`.
      - To do this, we need distances. The distance between two nodes in the same tree is their path length. The distance between a node in Tree1 and a node in Tree2 is `dist1(i, u) + 1 + dist2(v, k)`.
      - We can run a Breadth-First Search (BFS) from `i` in Tree1 to find `dist1(i, j)` for all `j`.
      - We can run a BFS from `v` in Tree2 to find `dist2(v, k)` for all `k`.
      - Sum up the nodes `j` in Tree1 where `dist1(i, j)` is even and nodes `k` in Tree2 where `dist1(i, u) + 1 + dist2(v, k)` is even.
    - Update `max_targets_for_i` with the maximum count found so far.
  - Store the result in `answer[i]`.

## Optimized Calculation per Query Node
This approach improves upon the naive brute-force by avoiding redundant calculations. We observe that the optimal choice of connection `(u, v)` allows us to gain a fixed maximum number of targets from Tree2, regardless of the query node `i`. We can pre-calculate this value. Then, for each query `i`, we only need to determine the number of its targets within Tree1, which can be found by a single graph traversal from `i`.
**Time:** O(n^2 + m). We perform one O(m) traversal for Tree2. Then, for each of the `n` nodes in Tree1, we perform an O(n) traversal. This leads to O(n*n) work for Tree1. · **Space:** O(n + m) for adjacency lists and BFS data structures.
**Pros:** Much faster than the naive brute-force approach.; Correctly identifies that the contribution from Tree2 can be calculated independently.
**Cons:** The time complexity is dominated by the O(n^2) part, which is too slow for the given constraints on `n`.
### Explanation
The core optimization is decoupling the problem. The total number of targets is `targets_in_T1 + targets_in_T2`. We want to maximize this sum. The choice of connection `(u, v)` affects `targets_in_T2`. A careful analysis shows that `max_{u,v}(targets_in_T2)` is a constant value for any `i`. We can pre-calculate this constant by finding the sizes of the two partitions of Tree2's bipartite coloring. Then, the problem reduces to, for each `i`, finding `targets_in_T1`. This is done by running a BFS from each `i`.

```java
class Solution {
    // Helper to run BFS and get distances
    private int[] bfs(int startNode, int numNodes, List<List<Integer>> adj) {
        int[] dist = new int[numNodes];
        Arrays.fill(dist, -1);
        Queue<Integer> q = new LinkedList<>();
        dist[startNode] = 0;
        q.offer(startNode);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.offer(v);
                }
            }
        }
        return dist;
    }

    public int[] maximizeTargetNodes(int n, int[][] edges1, int m, int[][] edges2) {
        List<List<Integer>> adj1 = new ArrayList<>();
        for (int i = 0; i < n; i++) adj1.add(new ArrayList<>());
        for (int[] edge : edges1) {
            adj1.get(edge[0]).add(edge[1]);
            adj1.get(edge[1]).add(edge[0]);
        }

        List<List<Integer>> adj2 = new ArrayList<>();
        for (int i = 0; i < m; i++) adj2.add(new ArrayList<>());
        for (int[] edge : edges2) {
            adj2.get(edge[0]).add(edge[1]);
            adj2.get(edge[1]).add(edge[0]);
        }

        // Pre-calculate max contribution from Tree2
        long[] counts2 = new long[2];
        int[] colors2 = new int[m];
        Arrays.fill(colors2, -1);
        Queue<Integer> q2 = new LinkedList<>();
        q2.offer(0);
        colors2[0] = 0;
        while(!q2.isEmpty()) {
            int u = q2.poll();
            counts2[colors2[u]]++;
            for(int v : adj2.get(u)) {
                if(colors2[v] == -1) {
                    colors2[v] = 1 - colors2[u];
                    q2.offer(v);
                }
            }
        }
        long maxContribT2 = Math.max(counts2[0], counts2[1]);

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            int[] distsFromI = bfs(i, n, adj1);
            long targetsInT1 = 0;
            for (int dist : distsFromI) {
                if (dist % 2 == 0) {
                    targetsInT1++;
                }
            }
            answer[i] = (int) (targetsInT1 + maxContribT2);
        }
        return answer;
    }
}
```
### Algorithm
- **Pre-computation for Tree2:**
  - Realize that the maximum number of target nodes from Tree2 is independent of the query node `i`.
  - Perform a single BFS/DFS on Tree2 to find its bipartite partitions. Count the number of nodes in each partition, `count2_even` and `count2_odd`.
  - The maximum contribution from Tree2 will always be `max(count2_even, count2_odd)`.
- **Calculation for each query `i`:**
  - For each node `i` from `0` to `n-1`:
    - Run a BFS/DFS on Tree1 starting from `i` to find the distance to all other nodes `j`.
    - Count the number of nodes `j` where `dist1(i, j)` is even. This gives the number of targets within Tree1.
    - The total maximum targets for `i` is the sum of targets from Tree1 and the pre-calculated maximum from Tree2.
  - Store this sum in `answer[i]`.

## Optimal Approach using Bipartite Coloring
This optimal approach fully leverages the properties of trees as bipartite graphs. Instead of re-calculating distances for each query, we can pre-calculate the bipartite partitions for both trees in linear time. The number of targets for any node `i` within its own tree is simply the size of the partition it belongs to. The maximum possible number of targets from the second tree is also a constant value determined by the sizes of its partitions. Combining these pre-calculated values gives the answer for each query in constant time.
**Time:** O(n + m). We perform one O(n) traversal for Tree1 and one O(m) traversal for Tree2. The final loop to compute answers is O(n). · **Space:** O(n + m) to store adjacency lists, color arrays, and BFS queues.
**Pros:** Optimal time and space complexity.; Solves the problem efficiently for large inputs.
**Cons:** The logic relies on understanding the relationship between distance parity and bipartite coloring, which may not be immediately obvious.
### Explanation
The key insight is that `dist(a, b) % 2 == (dist(root, a) % 2 + dist(root, b) % 2) % 2`. This means two nodes are at an even distance if and only if they have the same color in a 2-coloring of the graph. 

For any query `i`, the number of targets within Tree1 is the size of the partition `i` is in. We can find this by doing one traversal of Tree1 to color all nodes and count partition sizes. 

For Tree2, we want to maximize `|{k | (dist1(i, u) + 1 + dist2(v, k)) % 2 == 0}|`. By choosing `u` appropriately (e.g., `u=i` or a neighbor of `i`), we can make `dist1(i, u)` either even or odd. This allows us to choose whether we need `dist2(v, k)` to be odd or even. To maximize the count, we will always choose the one that gives more nodes, which is `max(count2_even, count2_odd)`. This value is constant for all `i`.

This reduces the entire problem to two initial traversals and then a simple loop, achieving linear time complexity.

```java
class Solution {
    public int[] maximizeTargetNodes(int n, int[][] edges1, int m, int[][] edges2) {
        // Build adjacency lists
        List<List<Integer>> adj1 = new ArrayList<>();
        for (int i = 0; i < n; i++) adj1.add(new ArrayList<>());
        for (int[] edge : edges1) {
            adj1.get(edge[0]).add(edge[1]);
            adj1.get(edge[1]).add(edge[0]);
        }

        List<List<Integer>> adj2 = new ArrayList<>();
        for (int i = 0; i < m; i++) adj2.add(new ArrayList<>());
        for (int[] edge : edges2) {
            adj2.get(edge[0]).add(edge[1]);
            adj2.get(edge[1]).add(edge[0]);
        }

        // Bipartite coloring for Tree 1
        int[] color1 = new int[n];
        Arrays.fill(color1, -1);
        Queue<Integer> q1 = new LinkedList<>();
        q1.offer(0);
        color1[0] = 0;
        while (!q1.isEmpty()) {
            int u = q1.poll();
            for (int v : adj1.get(u)) {
                if (color1[v] == -1) {
                    color1[v] = 1 - color1[u];
                    q1.offer(v);
                }
            }
        }
        long count1_color0 = 0;
        for (int c : color1) {
            if (c == 0) count1_color0++;
        }
        long count1_color1 = n - count1_color0;

        // Bipartite coloring for Tree 2
        long[] counts2 = new long[2];
        int[] colors2 = new int[m];
        Arrays.fill(colors2, -1);
        Queue<Integer> q2 = new LinkedList<>();
        q2.offer(0);
        colors2[0] = 0;
        while (!q2.isEmpty()) {
            int u = q2.poll();
            counts2[colors2[u]]++;
            for (int v : adj2.get(u)) {
                if (colors2[v] == -1) {
                    colors2[v] = 1 - colors2[u];
                    q2.offer(v);
                }
            }
        }
        long maxContribT2 = Math.max(counts2[0], counts2[1]);

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            long targetsInT1 = (color1[i] == 0) ? count1_color0 : count1_color1;
            answer[i] = (int) (targetsInT1 + maxContribT2);
        }

        return answer;
    }
}
```
### Algorithm
- **Bipartite Coloring:** A node `u` is target to `v` if the distance between them is even. In a bipartite graph (like a tree), this is equivalent to `u` and `v` being in the same color partition.
- **Algorithm Steps:**
  1. Build adjacency lists for both trees.
  2. Perform a single BFS/DFS on Tree1, starting from an arbitrary root (e.g., node 0), to establish a bipartite coloring. Store the color of each node in an array `color1`. Also, count the number of nodes in each partition: `count1_color0` and `count1_color1`.
  3. Perform a single BFS/DFS on Tree2 to find the sizes of its two partitions: `count2_color0` and `count2_color1`.
  4. The maximum number of target nodes from Tree2 is `max_contrib_T2 = max(count2_color0, count2_color1)`.
  5. For each node `i` from `0` to `n-1`:
     - The number of targets for `i` within Tree1 are all the nodes that have the same color as `i`. This is either `count1_color0` or `count1_color1`, which can be determined in O(1) using the pre-calculated `color1[i]`.
     - `answer[i] = (targets in Tree1) + max_contrib_T2`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int[] MaxTargetNodes(int[][] edges1, int[][] edges2) {
        var g1 = Build(edges1);
        var g2 = Build(edges2);
        int n = g1.Length, m = g2.Length;
        var c1 = new int[n];
        var c2 = new int[m];
        var cnt1 = new int[2];
        var cnt2 = new int[2];
        Dfs(g2, 0, -1, c2, 0, cnt2);
        Dfs(g1, 0, -1, c1, 0, cnt1);
        int t = Math.Max(cnt2[0], cnt2[1]);
        var ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = t + cnt1[c1[i]];
        }
        return ans;
    }
    private List < int > [] Build(int[][] edges) {
        int n = edges.Length + 1;
        var g = new List < int > [n];
        for (int i = 0; i < n; i++) {
            g[i] = new List < int > ();
        }
        foreach(var e in edges) {
            int a = e[0], b = e[1];
            g[a].Add(b);
            g[b].Add(a);
        }
        return g;
    }
    private void Dfs(List < int > [] g, int a, int fa, int[] c, int d, int[] cnt) {
        c[a] = d;
        cnt[d]++;
        foreach(var b in g[a]) {
            if (b != fa) {
                Dfs(g, b, a, c, d ^ 1, cnt);
            }
        }
    }
}
```

### Java

```java
class Solution {
public
  int[] maxTargetNodes(int[][] edges1, int[][] edges2) {
    var g1 = build(edges1);
    var g2 = build(edges2);
    int n = g1.length, m = g2.length;
    int[] c1 = new int[n];
    int[] c2 = new int[m];
    int[] cnt1 = new int[2];
    int[] cnt2 = new int[2];
    dfs(g2, 0, -1, c2, 0, cnt2);
    dfs(g1, 0, -1, c1, 0, cnt1);
    int t = Math.max(cnt2[0], cnt2[1]);
    int[] ans = new int[n];
    for (int i = 0; i < n; ++i) {
      ans[i] = t + cnt1[c1[i]];
    }
    return ans;
  }
private
  List<Integer>[] build(int[][] edges) {
    int n = edges.length + 1;
    List<Integer>[] g = new List[n];
    Arrays.setAll(g, i->new ArrayList<>());
    for (var e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    return g;
  } private void dfs(List<Integer>[] g, int a, int fa, int[] c, int d,
                     int[] cnt) {
    c[a] = d;
    cnt[d]++;
    for (int b : g[a]) {
      if (b != fa) {
        dfs(g, b, a, c, d ^ 1, cnt);
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> maxTargetNodes(vector<vector<int>> &edges1,
                             vector<vector<int>> &edges2) {
    auto g1 = build(edges1);
    auto g2 = build(edges2);
    int n = g1.size(), m = g2.size();
    vector<int> c1(n, 0), c2(m, 0);
    vector<int> cnt1(2, 0), cnt2(2, 0);
    dfs(g2, 0, -1, c2, 0, cnt2);
    dfs(g1, 0, -1, c1, 0, cnt1);
    int t = max(cnt2[0], cnt2[1]);
    vector<int> ans(n);
    for (int i = 0; i < n; ++i) {
      ans[i] = t + cnt1[c1[i]];
    }
    return ans;
  }

private:
  vector<vector<int>> build(const vector<vector<int>> &edges) {
    int n = edges.size() + 1;
    vector<vector<int>> g(n);
    for (const auto &e : edges) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      g[b].push_back(a);
    }
    return g;
  }
  void dfs(const vector<vector<int>> &g, int a, int fa, vector<int> &c, int d,
           vector<int> &cnt) {
    c[a] = d;
    cnt[d]++;
    for (int b : g[a]) {
      if (b != fa) {
        dfs(g, b, a, c, d ^ 1, cnt);
      }
    }
  }
};

```

### Python

```python
class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) -> List[int]: def build(edges: List[List[int]]) -> List[List[int]]: n = len(edges) + 1 g = [[] for _ in range(n)] for a, b in edges: g[a]. append(b) g[b]. append(a) return g def dfs(g: List[List[int]], a: int, fa: int, c: List[int], d: int, cnt: List[int]): c[a] = d cnt[d] += 1 for b in g[a]: if b != fa: dfs(g, b, a, c, d ^ 1, cnt) g1 = build(edges1) g2 = build(edges2) n, m = len(g1), len(g2) c1 = [0] * n c2 = [0] * m cnt1 = [0, 0] cnt2 = [0, 0] dfs(g2, 0, - 1, c2, 0, cnt2) dfs(g1, 0, - 1, c1, 0, cnt1) t = max(cnt2) return [t + cnt1[c1[i]] for i in range(n)]

```