LeetCode 3373 - Maximize the Number of Target Nodes After Connecting Trees II

The problem gives us two separate undirected trees. The first tree contains n nodes and the second tree contains m nodes. A tree is an acyclic connected graph, so every pair of nodes has exactly one simple path between them.

leetcodehardtreedepth-first-searchbreadth-first-search

LeetCode Problem 3373

Difficulty: 🔴 Hard
Topics: Tree, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

The problem gives us two separate undirected trees. The first tree contains n nodes and the second tree contains m nodes. A tree is an acyclic connected graph, so every pair of nodes has exactly one simple path between them.

For any two nodes u and v, node u is considered a target node to v if the number of edges on the path between them is even. Since the distance from a node to itself is 0, and 0 is even, every node is always target to itself.

For every node i in the first tree, we are allowed to temporarily connect exactly one node from the first tree to exactly one node from the second tree using a new edge. After adding this edge, we want to maximize the number of nodes that are target to node i.

The important detail is that each query is independent. After computing the answer for one node i, the added edge is removed before processing the next node.

The input consists of:

  • edges1, describing the first tree
  • edges2, describing the second tree

Each edge [a, b] means there is an undirected connection between nodes a and b.

The output should be an array answer where:

  • answer[i] is the maximum possible number of target nodes to node i after optimally connecting the two trees.

The constraints are very large:

  • n, m <= 100000

This immediately tells us that any solution involving repeated BFS or DFS from every node will likely be too slow. An O(n^2) or O(m^2) solution is infeasible because 100000^2 operations are far beyond acceptable limits.

There are several important observations and edge cases:

  • Trees are bipartite graphs, which means nodes can be split into two parity groups based on depth.
  • Distance parity between two nodes depends entirely on whether they belong to the same bipartite color.
  • The added edge always contributes exactly one extra edge, which flips parity between trees.
  • The queries are independent, so we do not need to maintain any persistent structure after each connection.
  • Extremely unbalanced trees, such as chains, must still run efficiently.
  • Very small trees, such as size 2, must also work correctly.

Approaches

Brute Force Approach

A direct brute-force solution would process each node i independently.

For each node i in the first tree:

  1. Try every possible node u in the first tree.
  2. Try every possible node v in the second tree.
  3. Add edge (u, v).
  4. Run BFS or DFS from i across the combined graph.
  5. Count how many nodes are at even distance from i.
  6. Keep the maximum result.

This works because it explicitly evaluates every possible connection and directly measures the number of target nodes.

However, this approach is far too slow.

If we run BFS for every pair (u, v):

  • There are O(n * m) possible connections.
  • Each BFS costs O(n + m).

Total complexity becomes:

O(n * m * (n + m))

With sizes up to 100000, this is impossible to run within time limits.

Key Insight

The key observation is that parity of distance in a tree depends entirely on bipartite coloring.

If we root a tree arbitrarily and assign:

  • color 0 to even-depth nodes
  • color 1 to odd-depth nodes

then:

  • two nodes have even distance if and only if they have the same color
  • two nodes have odd distance if and only if they have different colors

This transforms the problem from a shortest-path problem into a parity-counting problem.

Suppose node i in the first tree has color c.

Inside the first tree:

  • every node with color c is target to i
  • every node with opposite color is not

Now consider the second tree.

If we connect node u from the first tree to node v from the second tree, then any path from i to a node x in the second tree becomes:

distance(i, u) + 1 + distance(v, x)

The added edge contributes 1, which flips parity.

To make the total distance even:

distance(i, u) parity != distance(v, x) parity

Using bipartite coloring, this means:

  • nodes in the second tree that are target to i are exactly one color class of the second tree
  • we can choose which color class by selecting the connection appropriately

Therefore:

  • contribution from first tree is fixed for node i
  • contribution from second tree is simply the larger bipartite partition size

This gives a very efficient solution.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m * (n + m)) O(n + m) Tries every connection and runs traversal each time
Optimal O(n + m) O(n + m) Uses bipartite parity properties of trees

Algorithm Walkthrough

Step 1: Build adjacency lists

Convert both edge lists into adjacency lists.

This allows efficient traversal of each tree using DFS or BFS.

Step 2: Bipartite-color the first tree

Run DFS from node 0.

Assign:

  • color 0 to the root
  • alternate colors for neighbors

While traversing:

  • count how many nodes belong to color 0
  • count how many belong to color 1

For every node i, store its color.

This works because trees are bipartite.

Step 3: Compute target counts inside the first tree

If node i has:

  • color 0, then all color 0 nodes are at even distance
  • color 1, then all color 1 nodes are at even distance

Therefore:

sameColorCount[i] =
    count0 if color[i] == 0
    count1 otherwise

This is the number of target nodes already reachable inside the first tree.

Step 4: Bipartite-color the second tree

Repeat the same DFS process for the second tree.

Again compute:

  • number of color 0 nodes
  • number of color 1 nodes

Step 5: Compute the best possible contribution from the second tree

Because the added edge flips parity, we can make node i target exactly one bipartite partition of the second tree.

We are free to choose the connection optimally.

Therefore the maximum possible contribution from the second tree is:

bestSecond = max(count0Second, count1Second)

Step 6: Build the final answer

For every node i:

answer[i] = sameColorCount[i] + bestSecond

Return the resulting array.

Why it works

In a bipartite tree, parity of distance is determined entirely by node colors.

Nodes with the same color are always at even distance.

The added bridge edge contributes exactly one extra edge, which flips parity between the two trees.

By choosing the connection endpoints appropriately, we can decide which color partition of the second tree becomes even-distance reachable from node i.

Therefore the optimal strategy is always to select the larger partition of the second tree, while the contribution from the first tree is fixed.

This guarantees the algorithm always produces the maximum possible number of target nodes.

Python Solution

from typing import List
from collections import deque

class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:
        def build_graph(size: int, edges: List[List[int]]) -> List[List[int]]:
            graph = [[] for _ in range(size)]

            for u, v in edges:
                graph[u].append(v)
                graph[v].append(u)

            return graph

        def color_tree(graph: List[List[int]]):
            n = len(graph)

            color = [-1] * n
            counts = [0, 0]

            queue = deque([0])
            color[0] = 0
            counts[0] = 1

            while queue:
                node = queue.popleft()

                for neighbor in graph[node]:
                    if color[neighbor] == -1:
                        color[neighbor] = color[node] ^ 1
                        counts[color[neighbor]] += 1
                        queue.append(neighbor)

            return color, counts

        n = len(edges1) + 1
        m = len(edges2) + 1

        graph1 = build_graph(n, edges1)
        graph2 = build_graph(m, edges2)

        color1, counts1 = color_tree(graph1)
        _, counts2 = color_tree(graph2)

        best_second = max(counts2)

        answer = []

        for node in range(n):
            answer.append(counts1[color1[node]] + best_second)

        return answer

The implementation begins by constructing adjacency lists for both trees. Since trees are sparse graphs with exactly n - 1 edges, adjacency lists are the most efficient representation.

The color_tree function performs BFS to assign bipartite colors. The root starts with color 0, and every neighboring node receives the opposite color using XOR with 1.

While coloring the tree, the function also counts how many nodes belong to each partition. This is important because nodes with the same color always have even distance between them.

For the first tree, the algorithm stores each node's color so it can determine how many target nodes already exist inside the tree.

For the second tree, only the partition sizes matter. Since we can choose the connection optimally, we simply take the larger partition.

Finally, each answer is computed by adding:

  • nodes in the same partition as i in the first tree
  • the best partition size from the second tree

Go Solution

package main

func maxTargetNodes(edges1 [][]int, edges2 [][]int) []int {
	buildGraph := func(size int, edges [][]int) [][]int {
		graph := make([][]int, size)

		for _, edge := range edges {
			u, v := edge[0], edge[1]
			graph[u] = append(graph[u], v)
			graph[v] = append(graph[v], u)
		}

		return graph
	}

	colorTree := func(graph [][]int) ([]int, [2]int) {
		n := len(graph)

		color := make([]int, n)
		for i := range color {
			color[i] = -1
		}

		var counts [2]int

		queue := make([]int, 0)
		queue = append(queue, 0)

		color[0] = 0
		counts[0] = 1

		head := 0

		for head < len(queue) {
			node := queue[head]
			head++

			for _, neighbor := range graph[node] {
				if color[neighbor] == -1 {
					color[neighbor] = color[node] ^ 1
					counts[color[neighbor]]++

					queue = append(queue, neighbor)
				}
			}
		}

		return color, counts
	}

	n := len(edges1) + 1
	m := len(edges2) + 1

	graph1 := buildGraph(n, edges1)
	graph2 := buildGraph(m, edges2)

	color1, counts1 := colorTree(graph1)
	_, counts2 := colorTree(graph2)

	bestSecond := counts2[0]
	if counts2[1] > bestSecond {
		bestSecond = counts2[1]
	}

	answer := make([]int, n)

	for i := 0; i < n; i++ {
		answer[i] = counts1[color1[i]] + bestSecond
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

Instead of Python lists and deque, Go uses slices and a manual queue index called head. This avoids inefficient slice shifting operations.

The color array is initialized with -1 to indicate unvisited nodes.

Go integers are sufficient because the maximum answer is at most n + m, which easily fits within 32-bit integer limits.

Worked Examples

Example 1

edges1 = [[0,1],[0,2],[2,3],[2,4]]
edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]

First Tree Coloring

Starting BFS from node 0:

Node Color
0 0
1 1
2 1
3 0
4 0

Partition sizes:

Color Count
0 3
1 2

Therefore:

Node Same-color nodes
0 3
1 2
2 2
3 3
4 3

Second Tree Coloring

One valid coloring:

Node Color
0 0
1 1
2 1
3 1
4 0
5 1
6 1
7 0

Partition sizes:

Color Count
0 3
1 5

Best contribution:

bestSecond = 5

Final Answers

Node First Tree Contribution Second Tree Contribution Total
0 3 5 8
1 2 5 7
2 2 5 7
3 3 5 8
4 3 5 8

Final result:

[8,7,7,8,8]

Example 2

edges1 = [[0,1],[0,2],[0,3],[0,4]]
edges2 = [[0,1],[1,2],[2,3]]

First Tree Coloring

Node Color
0 0
1 1
2 1
3 1
4 1

Partition sizes:

Color Count
0 1
1 4

Second Tree Coloring

Node Color
0 0
1 1
2 0
3 1

Partition sizes:

Color Count
0 2
1 2

Best contribution:

2

Final Answers

Node First Tree Contribution Second Tree Contribution Total
0 1 2 3
1 4 2 6
2 4 2 6
3 4 2 6
4 4 2 6

Final result:

[3,6,6,6,6]

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each tree is traversed exactly once
Space O(n + m) Adjacency lists, color arrays, and BFS queue

The algorithm performs a single BFS traversal on each tree.

Since a tree with k nodes has exactly k - 1 edges, traversing the entire graph costs O(k).

No nested traversals or repeated shortest-path computations occur, which allows the solution to scale efficiently to the maximum constraint size.

Test Cases

from typing import List

class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:
        from collections import deque

        def build_graph(size, edges):
            graph = [[] for _ in range(size)]

            for u, v in edges:
                graph[u].append(v)
                graph[v].append(u)

            return graph

        def color_tree(graph):
            n = len(graph)

            color = [-1] * n
            counts = [0, 0]

            queue = deque([0])

            color[0] = 0
            counts[0] = 1

            while queue:
                node = queue.popleft()

                for neighbor in graph[node]:
                    if color[neighbor] == -1:
                        color[neighbor] = color[node] ^ 1
                        counts[color[neighbor]] += 1
                        queue.append(neighbor)

            return color, counts

        n = len(edges1) + 1
        m = len(edges2) + 1

        graph1 = build_graph(n, edges1)
        graph2 = build_graph(m, edges2)

        color1, counts1 = color_tree(graph1)
        _, counts2 = color_tree(graph2)

        best_second = max(counts2)

        return [
            counts1[color1[i]] + best_second
            for i in range(n)
        ]

sol = Solution()

# Example 1
assert sol.maxTargetNodes(
    [[0,1],[0,2],[2,3],[2,4]],
    [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]
) == [8,7,7,8,8]

# Example 2
assert sol.maxTargetNodes(
    [[0,1],[0,2],[0,3],[0,4]],
    [[0,1],[1,2],[2,3]]
) == [3,6,6,6,6]

# Minimum size trees
assert sol.maxTargetNodes(
    [[0,1]],
    [[0,1]]
) == [2,2]

# Chain trees
assert sol.maxTargetNodes(
    [[0,1],[1,2],[2,3]],
    [[0,1],[1,2]]
) == [4,3,4,3]

# Star-shaped first tree
assert sol.maxTargetNodes(
    [[0,1],[0,2],[0,3],[0,4],[0,5]],
    [[0,1]]
) == [2,6,6,6,6,6]

# Balanced binary tree
assert sol.maxTargetNodes(
    [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]],
    [[0,1],[1,2],[2,3]]
) == [6,5,5,6,6,6,6]

# Second tree heavily unbalanced
assert sol.maxTargetNodes(
    [[0,1],[1,2]],
    [[0,1],[1,2],[2,3],[3,4],[4,5]]
) == [6,5,6]

print("All tests passed.")

Test Summary

Test Why
Example 1 Verifies the main sample from the problem
Example 2 Verifies star-shaped structure behavior
Minimum size trees Confirms correctness on smallest valid input
Chain trees Tests alternating parity along long paths
Star-shaped first tree Tests highly skewed bipartite partitions
Balanced binary tree Tests more symmetric structures
Second tree heavily unbalanced Verifies choosing the larger partition

Edge Cases

One important edge case occurs when the tree has only two nodes. In this situation, each bipartite partition contains exactly one node. A buggy implementation might incorrectly assume larger partition sizes or mishandle indexing. The implementation handles this naturally because BFS coloring works correctly even on the smallest valid tree.

Another important case is a chain-shaped tree. In a long path, node parity alternates continuously. A naive implementation based on repeated shortest-path calculations could become quadratic. The optimized solution avoids this entirely because parity is determined only by coloring, not by explicitly computing all distances.

A third important edge case is a highly unbalanced bipartite partition, such as a star graph. In a star centered at node 0, one partition contains only the center while the other contains all leaves. The algorithm correctly chooses the larger partition from the second tree, maximizing the number of target nodes after connection.

A final subtle edge case involves independent queries. Since every query removes the added edge afterward, we must not permanently modify either tree. The implementation never physically inserts edges. Instead, it uses the parity observation to compute results mathematically, which automatically preserves independence between queries.