#3372

Maximize the Number of Target Nodes After Connecting Trees I

specialist · 615 · lc medium +29 · 69.5% accepted · 445 likes · top 77%

Description

Two undirected trees exist with n and m nodes labeled in ranges [0, n - 1] and [0, m - 1] respectively.

You are given 2D arrays edges1 and edges2 of lengths n - 1 and m - 1, where edges1[i] = [ai, bi] and edges2[i] = [ui, vi] describe the edges of each tree. You are also given an integer k.

Node u is a target of node v if the path between them uses at most k edges. Every node targets itself.

Return an array answer of n integers, where answer[i] is the maximum number of nodes that can be targeted by node i of the first tree if you connect one node from the first tree to one node in the second tree.

Each query is independent: the added edge is removed before the next query.

Code

1

2

3

class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]], k: int) -> List[int]:

class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]], k: int) -> List[int]: