Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

3645. Maximize the Number of Target Nodes After Connecting Trees II

My accepted Python solution to LeetCode problem 3645, Maximize the Number of Target Nodes After Connecting Trees II, running in 493ms.

  • Difficulty: Hard
  • Python
  • Runtime 493ms
  • Memory 81.5MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 493ms, memory 81.5MB, accepted 2025-12-31.

python
class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:
        from collections import defaultdict, deque
        
        def color_tree(edges):
            if not edges:
                return [0], {0: 1, 1: 0}
            n = len(edges) + 1
            graph = defaultdict(list)
            for u, v in edges:
                graph[u].append(v)
                graph[v].append(u)
            colors = [-1] * n
            colors[0] = 0
            q = deque([0])
            cnt = {0: 0, 1: 0}
            while q:
                node = q.popleft()
                cnt[colors[node]] += 1
                for nei in graph[node]:
                    if colors[nei] == -1:
                        colors[nei] = 1 - colors[node]
                        q.append(nei)
            return colors, cnt
        
        colors1, cnt1 = color_tree(edges1)
        colors2, cnt2 = color_tree(edges2)
        
        # For tree2, we want max of opposite color (since we add 1 edge)
        max_tree2 = max(cnt2[0], cnt2[1])
        
        # For each node in tree1, answer is count of same color + max from tree2
        n = len(colors1)
        return [cnt1[colors1[i]] + max_tree2 for i in range(n)]

Source