#3373

Maximize the Number of Target Nodes After Connecting Trees II

specialist · 960 · lc hard +32 · 73.2% accepted · 371 likes · top 83%

Description

Two undirected trees exist with n and m nodes labeled from [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.

Node u is a target of node v if the path between them has an even number of 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]]) -> List[int]:

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