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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize the Number of Target Nodes After Connecting Trees I

Number: 3633

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given two undirected trees – one with n nodes (labeled 0 to n - 1) and another with m nodes (labeled 0 to m - 1) – and an integer k, each tree is provided as an edge list. For any two nodes u and v (which may be in different trees after an added connecting edge) we call v “target” to u if the number of edges on the path from u to v is less than or equal to k. For every node i in the first tree, you are allowed to add one extra edge connecting any node in the first tree and any node in the second tree (queries are independent). The goal is to maximize the total number of nodes that become target to node i, counting those in the first tree (using tree1’s intrinsic connectivity) as well as the nodes in the second tree (reached via the added connecting edge) and return an answer array of length n.

Key Insights

  • In tree1, for any node i, one may precompute the number of nodes reachable within k edges (by a simple BFS per node).
  • The added connecting edge always “costs” 1 edge. When connecting node i (or some other node u in tree1) to a node v in tree2, the remaining “budget” to travel inside tree2 is k - (distance from i to u + 1).
  • Because trees have the property that distance(i, i) is 0, the optimal solution is always achieved by choosing u = i. This gives the maximum remaining budget for tree2 nodes, which is (k - 1).
  • Precompute for tree2, for every node, the number of nodes reachable within a radius of (k - 1) (if k ≥ 1). Then, take the maximum among these counts (denoted as best2). In case k is 0, no connection is allowed so only tree1’s reachable nodes are counted.
  • Thus, for each node i in tree1, the answer is: • tree1_reachable_count(i, k) + (if k ≥ 1 then best2 else 0).

Space and Time Complexity

Time Complexity: O(n^2 + m^2) in the worst-case, due to performing BFS from every node in tree1 and tree2. Space Complexity: O(n + m) for storing the graphs and the BFS queue at any given time.

Solution

We start by building the adjacency lists for both trees based on the given edge arrays. For each node in tree1, run a BFS to count how many nodes are at a distance ≤ k (this gives the tree1 contribution per node).

For tree2, since the connecting edge uses up 1 step, we are interested in the maximum number of nodes reachable with a remaining budget of (k-1). Run a BFS from every node in tree2 (if k ≥ 1) to compute the reachable count, and maintain the maximum value among all nodes (best2).

Since the optimal connection on tree1 is achieved by choosing the same node i (giving a cost of 0 before the connection), every answer for node i is simply the sum of:  • The count of tree1 nodes reachable within k from i.  • best2 (the optimal tree2 reachable count with radius k-1) if k ≥ 1; otherwise 0.

This greedy observation avoids iterating over all potential connecting nodes in tree1, and simplifies the solution considerably.

Code Solutions

# Python solution using BFS for both trees.

from collections import deque

def maximizeTargetNodes(edges1, edges2, k):
    # Build graph for tree1 (n nodes) and tree2 (m nodes)
    n = max(max(u, v) for u, v in edges1) + 1
    m = max(max(u, v) for u, v in edges2) + 1
    
    graph1 = [[] for _ in range(n)]
    for u, v in edges1:
        graph1[u].append(v)
        graph1[v].append(u)
    
    graph2 = [[] for _ in range(m)]
    for u, v in edges2:
        graph2[u].append(v)
        graph2[v].append(u)
    
    # Function to count nodes within given radius using BFS in a given graph.
    def bfs_count(graph, start, radius):
        visited = [False] * len(graph)
        q = deque()
        q.append((start, 0))
        visited[start] = True
        count = 0
        while q:
            node, dist = q.popleft()
            if dist > radius:
                continue
            count += 1
            for nei in graph[node]:
                if not visited[nei]:
                    visited[nei] = True
                    q.append((nei, dist + 1))
        return count

    # Precompute reachable counts for every node in tree1 with radius = k.
    tree1_counts = [0] * n
    for i in range(n):
        tree1_counts[i] = bfs_count(graph1, i, k)
    
    # Compute best2: maximum reachable count in tree2 with radius = (k-1).
    best2 = 0
    # Only compute if k is at least 1 (since connection edge costs 1).
    if k >= 1:
        remaining = k - 1
        for i in range(m):
            count = bfs_count(graph2, i, remaining)
            best2 = max(best2, count)
    
    # Calculate answer for each node in tree1.
    answer = [0] * n
    for i in range(n):
        # If k == 0, connection not possible so only tree1 reachable nodes count.
        answer[i] = tree1_counts[i] + (best2 if k >= 1 else 0)
    
    return answer

# 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(maximizeTargetNodes(edges1, edges2, k))  # Expected output [9,7,9,8,8]
← Back to All Questions