Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Connecting the trees does not change distances within the first tree. For a queried node, attaching the new edge directly to it leaves the largest possible distance budget in the second tree: k - 1. Attaching elsewhere would spend extra steps before crossing and cannot reach more second-tree nodes.

Approach

Build adjacency lists for both trees. Use a breadth-first search that counts nodes through a given distance limit, carrying the parent to avoid traversing an edge backward. A tree needs no additional visited set when the parent is excluded.

When k > 0, run this search from every second-tree node with radius k - 1 and retain the largest count. For each first-tree node, count nodes within radius k and add that shared maximum. When k = 0, use zero as the second-tree contribution.

Each query may choose its own connecting edge independently, so the best second-tree attachment can be reused in every answer without imposing a single common edge on all queries.

class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]], k: 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, limit):
            q = deque([(start, 0, -1)]) # node, level, par
            count = 0

            while q:
                node, level, par = q.popleft()
                count += 1
                for nei in adj[node]:
                    if level < limit and nei != par:
                        q.append((nei, level + 1, node))
            
            return count

        mx2 = 0
        if k > 0:
            for i in range(m + 1):
                mx2 = max(mx2, bfs(i, adj2, k - 1))
        
        res = [0] * (n + 1)
        for i in range(n + 1):
            res[i] = bfs(i, adj1, k) + mx2
        
        return res

Complexity analysis

Let N and M be the node counts of the two trees. Running a bounded BFS from every node takes O(N^2 + M^2) time and O(N + M) auxiliary space, excluding the O(N) returned array. A negative second-tree radius when k = 0 contributes zero nodes.