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 II

Number: 3645

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two undirected trees – one with n nodes (labeled 0 to n‑1) and the other with m nodes (labeled 0 to m‑1) – and their respective edge lists, you need to answer n queries. For each node i in the first tree, you are allowed to add one extra edge that connects node i from the first tree to any node from the second tree. After connecting the two trees, a node u is called target to node v if the path from u to v (in the combined tree) uses an even number of edges (note that every node is always target to itself). For each node i in the first tree (each query considered independently), return the maximum possible number of nodes that can be target to i when you choose the best connecting edge.

Key Insights

  • Trees are bipartite: when performing a DFS/BFS from any starting node, nodes can be colored into two groups, so that the distance parity (even/odd) is preserved.
  • In any tree, two nodes have an even distance if and only if they belong to the same bipartite group (same color).
  • For tree1, if you precompute the partition sizes, then for any query node i its target nodes in tree1 are exactly the nodes in the same partition (including itself).
  • In tree2, when you connect a node i from tree1 to some node j in tree2, the extra edge makes any node in tree2 target to i if it is at an odd distance from j. Since tree2 is bipartite, if j belongs to one partition then the target nodes in tree2 (relative to j) are exactly the nodes in the opposite partition.
  • Thus, you can choose for tree2 the connecting node j which gives the maximum count between the two partitions.
  • The overall maximum target count for node i is the sum of the number of nodes in the same partition in tree1 and the maximum of the two partition counts in tree2.

Space and Time Complexity

Time Complexity: O(n + m), where n and m are the number of nodes in tree1 and tree2 respectively. We DFS/BFS each tree once. Space Complexity: O(n + m) to store the adjacency lists and partition/color arrays.

Solution

We first perform a DFS/BFS on both trees to assign each node a color (0 or 1) representing its parity. In tree1, the target nodes for any node i are those nodes with the same color as i. Let cnt1_0 and cnt1_1 denote the number of nodes in tree1 with colors 0 and 1, respectively. For tree2, we similarly compute cnt2_0 and cnt2_1. In a query for node i, after the connection:

  • Its tree1 target count is cnt1_0 if its color is 0 (or cnt1_1 if its color is 1).
  • In tree2, if you connect with a node from color 0 then the odd-distance nodes from that node will be all nodes from color 1 (i.e. cnt2_1); if you connect with a node from color 1 then the odd-distance nodes will be all nodes from color 0 (i.e. cnt2_0). Therefore the maximum additional count achievable from tree2 is max(cnt2_0, cnt2_1). Thus, for every node i in tree1, the answer is: answer[i] = (if color(i) == 0 then cnt1_0 else cnt1_1) + max(cnt2_0, cnt2_1).

The main challenge is correctly coloring both trees and computing the counts. This solution uses DFS or BFS to color the trees and simple aggregation to compute counts — a neat application of bipartite properties.

Code Solutions

# Python solution using DFS
def maximize_target_nodes(edges1, edges2):
    from collections import defaultdict, deque
    
    # Function to build graph from edges list
    def build_graph(num_nodes, edges):
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        return graph

    # Color the tree using BFS and compute counts in each partition
    def bfs_color(num_nodes, graph):
        colors = [-1] * num_nodes  # -1 means unvisited, colors: 0 or 1
        count = [0, 0]
        # Start from node 0 (any arbitrary node works in a tree)
        queue = deque([0])
        colors[0] = 0
        count[0] += 1
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if colors[neighbor] == -1:
                    colors[neighbor] = colors[node] ^ 1  # Flip color
                    count[colors[neighbor]] += 1
                    queue.append(neighbor)
        return colors, count

    n = len(edges1) + 1
    m = len(edges2) + 1

    graph1 = build_graph(n, edges1)
    graph2 = build_graph(m, edges2)

    colors1, count1 = bfs_color(n, graph1)
    colors2, count2 = bfs_color(m, graph2)

    # The optimal extra target nodes in tree2 = max(count2[0], count2[1])
    best_tree2 = max(count2)
    
    # For each node in tree1, calculate answer based on its color.
    answer = []
    for i in range(n):
        answer.append((count1[colors1[i]]) + best_tree2)
    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]]
print(maximize_target_nodes(edges1, edges2))
← Back to All Questions