We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximize the Number of Target Nodes After Connecting Trees I

Difficulty: Medium

Problem Description

Given two undirected trees with distinct labels, you need to determine the maximum possible number of target nodes for each node in the first tree when connected to a node in the second tree. A node is considered targetable if the number of edges on the path from one node to another is less than or equal to a given integer k.

Key Insights

  • Each tree has distinct nodes and edges connecting them.
  • A node in the first tree can connect to any node in the second tree.
  • The targetability of a node depends on the distance (number of edges) to other nodes in the second tree, constrained by k.
  • The problem requires efficient traversal of both trees to calculate distances.

Space and Time Complexity

Time Complexity: O(n + m) for each query, where n and m are the number of nodes in the first and second trees, respectively. This accounts for the traversal of both trees. Space Complexity: O(n + m) for storing the adjacency lists of both trees.

Solution

To solve this problem, we can use Breadth-First Search (BFS) or Depth-First Search (DFS) to calculate the distances of all nodes from a given starting node in both trees. For each node in the first tree, we will determine how many nodes in the second tree are reachable within k edges.

  1. Construct adjacency lists for both trees from the given edge lists.
  2. For each node in the first tree:
    • Perform BFS/DFS from that node to calculate distances to all nodes in the second tree.
    • Count how many nodes in the second tree can be reached within k edges.
  3. Store the results for each node in the first tree.

Code Solutions

from collections import defaultdict, deque

def count_target_nodes(edges1, edges2, k):
    # Build adjacency list for tree 1
    tree1 = defaultdict(list)
    for u, v in edges1:
        tree1[u].append(v)
        tree1[v].append(u)

    # Build adjacency list for tree 2
    tree2 = defaultdict(list)
    for u, v in edges2:
        tree2[u].append(v)
        tree2[v].append(u)

    # Function to count reachable nodes within distance k
    def bfs_count(start_node, tree, max_distance):
        queue = deque([(start_node, 0)])  # (current_node, current_distance)
        visited = set([start_node])
        count = 1  # Count the starting node

        while queue:
            node, distance = queue.popleft()
            if distance < max_distance:
                for neighbor in tree[node]:
                    if neighbor not in visited:
                        visited.add(neighbor)
                        count += 1
                        queue.append((neighbor, distance + 1))

        return count

    # Result array
    result = []
    for node in range(len(edges1) + 1):  # For each node in tree 1
        reachable_count = bfs_count(node, tree2, k)
        result.append(reachable_count)

    return result

# Example usage
edges1 = [[0,1],[0,2],[2,3],[2,4]]
edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]
k = 2
print(count_target_nodes(edges1, edges2, k))
← Back to All Questions