Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Color each tree by distance parity from any root. Two nodes have even distance exactly when they have the same color. Thus a queried node's first-tree contribution is simply the size of its own color class. The connecting edge lets us choose which second-tree color class becomes even-distance from it.

Approach

Run a breadth-first traversal from node zero in each tree, assigning alternating parity and counting the two color classes. Python carries the parent to avoid traversing backward and stores class membership in sets; JavaScript uses a visited set, class counts and a parity array. Retain each first-tree node's class membership.

Take the larger class size in the second tree. For each first-tree node, return its own class size plus that maximum. To realize this choice, connect the queried node directly to a second-tree node in the opposite class from the desired targets. The added edge flips parity, making those targets even-distance away. Both second-tree classes are nonempty under the node-count constraints.

The edge can be chosen independently for each query, and no edge can contribute more than the larger second-tree class, so the construction meets the upper bound.

class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:
        def build_adj(edges):
            adj = defaultdict(list)
            for a, b in edges:
                adj[a].append(b)
                adj[b].append(a)
            return adj
        
        adj1, adj2 = build_adj(edges1), build_adj(edges2)

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

        def bfs(start, adj):
            q = deque([(start, 0, -1)]) # node, parity, parent
            even, odd = set(), set()

            while q:
                node, parity, parent = q.popleft()
                if parity == 0: even.add(node)
                else: odd.add(node)

                for nei in adj[node]:
                    if nei != parent:
                        new_parity = 0 if parity == 1 else 1
                        q.append((nei, new_parity, node))
            
            return even, odd
        
        even2, odd2 = bfs(0, adj2)
        even1, odd1 = bfs(0, adj1)
        mx2 = max(len(even2), len(odd2))

        res = [0] * (n + 1)
        for i in range(n + 1):
            if i in even1: res[i] = len(even1) + mx2
            else: res[i] = len(odd1) + mx2
            
        return res

Complexity analysis

Let N and M be the two tree node counts. One BFS bipartition of each tree plus the final per-node lookup takes O(N + M) time and O(N + M) auxiliary space for adjacency, queues, and parity colors.