Maximize the Number of Target Nodes After Connecting Trees II - Problem

There exist two undirected trees with n and m nodes, labeled from [0, n - 1] and [0, m - 1], respectively.

You are given two 2D integer arrays edges1 and edges2 of lengths n - 1 and m - 1, respectively, where edges1[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the first tree and edges2[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the second tree.

Node u is target to node v if the number of edges on the path from u to v is even. Note that a node is always target to itself.

Return an array of n integers answer, where answer[i] is the maximum possible number of nodes that are target to node i of the first tree if you had to connect one node from the first tree to another node in the second tree.

Note that queries are independent from each other. That is, for every query you will remove the added edge before proceeding to the next query.

Input & Output

Example 1 — Basic Two-Node Trees

$ Input: edges1 = [[0,1]], edges2 = [[0,1]]

› Output: [3,3]

💡 Note: Each tree has 2 nodes. When we connect them optimally, each node can reach 3 target nodes total (including nodes at even distances through the bridge connection).

Example 2 — Single Node Trees

$ Input: edges1 = [], edges2 = []

› Output: [2]

💡 Note: Each tree has only 1 node. When connected, node 0 from tree1 can reach itself (distance 0, even) and the single node from tree2 (distance 1+0=1, odd). Actually, distance 1 is odd, so only itself at distance 0. The bridge adds 1 more reachable target.

Example 3 — Larger Trees

$ Input: edges1 = [[0,1],[1,2]], edges2 = [[0,1],[1,2]]

› Output: [4,4,4]

💡 Note: Linear trees with 3 nodes each. Optimal bridge connections allow each query node to reach maximum target nodes with even path lengths.

Constraints

1 ≤ n, m ≤ 1000
edges1.length = n - 1
edges2.length = m - 1
0 ≤ a_i, b_i < n
0 ≤ u_i, v_i < m
The input ensures that edges1 and edges2 represent valid trees

Visualization

Tap to expand

Asked in

G Google 12 f Meta 8 a Amazon 6

This tree problem requires understanding bipartite properties and optimal bridge placement. The key insight is that trees naturally partition nodes into two groups based on distance parity. The optimized approach uses tree re-rooting to efficiently compute target counts. Time: O(n² + m²), Space: O(n + m).

Common Approaches

✓ One Pass Hash

⏱️ Time: N/A Space: N/A

Brute Force with DFS

⏱️ Time: O(n²·m²) Space: O(n + m)

For each node in the first tree, try connecting every pair of nodes between the two trees. For each connection, perform DFS to count nodes reachable with even path lengths.

Tree Re-rooting with Bipartite Analysis

⏱️ Time: O(n² + m²) Space: O(n + m)

Recognize that trees are bipartite graphs. Precompute the bipartite partition for each tree, then use tree re-rooting technique to efficiently compute answers for all nodes without redundant DFS calls.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000

static int adj1[MAX_N][MAX_N];
static int adj_count1[MAX_N];
static int adj2[MAX_N][MAX_N];
static int adj_count2[MAX_N];
static int queue[MAX_N];
static int dist[MAX_N];

int countEvenDistance(int adj[][MAX_N], int adj_count[], int n, int start) {
    for (int i = 0; i < n; i++) {
        dist[i] = -1;
    }
    
    int front = 0, rear = 0;
    queue[rear++] = start;
    dist[start] = 0;
    
    int count = 0;
    while (front < rear) {
        int u = queue[front++];
        
        if (dist[u] % 2 == 0) count++;
        
        for (int i = 0; i < adj_count[u]; i++) {
            int v = adj[u][i];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue[rear++] = v;
            }
        }
    }
    
    return count;
}

void countEvenOddDistance(int adj[][MAX_N], int adj_count[], int n, int start, int* even_count, int* odd_count) {
    for (int i = 0; i < n; i++) {
        dist[i] = -1;
    }
    
    int front = 0, rear = 0;
    queue[rear++] = start;
    dist[start] = 0;
    
    *even_count = 0;
    *odd_count = 0;
    while (front < rear) {
        int u = queue[front++];
        
        if (dist[u] % 2 == 0) (*even_count)++;
        else (*odd_count)++;
        
        for (int i = 0; i < adj_count[u]; i++) {
            int v = adj[u][i];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                queue[rear++] = v;
            }
        }
    }
}

void parseEdges(char* s, int edges[][2], int* edge_count) {
    *edge_count = 0;
    if (strcmp(s, "[]") == 0) return;
    
    int len = strlen(s);
    int pos = 1; // skip first '['
    
    while (pos < len - 1) { // skip last ']'
        // Find next '['
        while (pos < len && s[pos] != '[') pos++;
        if (pos >= len) break;
        
        pos++; // skip '['
        
        // Parse first number
        int a = 0;
        while (pos < len && s[pos] >= '0' && s[pos] <= '9') {
            a = a * 10 + (s[pos] - '0');
            pos++;
        }
        
        // Skip comma
        while (pos < len && s[pos] != ',' && s[pos] >= '0' && s[pos] <= '9') pos++;
        if (pos < len && s[pos] == ',') pos++;
        
        // Parse second number
        int b = 0;
        while (pos < len && s[pos] >= '0' && s[pos] <= '9') {
            b = b * 10 + (s[pos] - '0');
            pos++;
        }
        
        edges[*edge_count][0] = a;
        edges[*edge_count][1] = b;
        (*edge_count)++;
        
        // Find next ']'
        while (pos < len && s[pos] != ']') pos++;
        if (pos < len) pos++;
    }
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    // Remove newlines
    line1[strcspn(line1, "\n")] = 0;
    line2[strcspn(line2, "\n")] = 0;
    
    int edges1[MAX_N][2], edges2[MAX_N][2];
    int edge_count1, edge_count2;
    
    parseEdges(line1, edges1, &edge_count1);
    parseEdges(line2, edges2, &edge_count2);
    
    int n = edge_count1 + 1;
    int m = edge_count2 + 1;
    
    // Build adjacency lists
    for (int i = 0; i < n; i++) {
        adj_count1[i] = 0;
    }
    for (int i = 0; i < m; i++) {
        adj_count2[i] = 0;
    }
    
    for (int i = 0; i < edge_count1; i++) {
        int u = edges1[i][0], v = edges1[i][1];
        adj1[u][adj_count1[u]++] = v;
        adj1[v][adj_count1[v]++] = u;
    }
    for (int i = 0; i < edge_count2; i++) {
        int u = edges2[i][0], v = edges2[i][1];
        adj2[u][adj_count2[u]++] = v;
        adj2[v][adj_count2[v]++] = u;
    }
    
    // For each node in tree1, count nodes at even distances
    int tree1_even[MAX_N];
    for (int i = 0; i < n; i++) {
        tree1_even[i] = countEvenDistance(adj1, adj_count1, n, i);
    }
    
    // For each node in tree2, count nodes at even and odd distances
    int tree2_even[MAX_N], tree2_odd[MAX_N];
    for (int i = 0; i < m; i++) {
        countEvenOddDistance(adj2, adj_count2, m, i, &tree2_even[i], &tree2_odd[i]);
    }
    
    // Find max even and odd counts from tree2
    int max_tree2_even = 0, max_tree2_odd = 0;
    for (int i = 0; i < m; i++) {
        if (tree2_even[i] > max_tree2_even) max_tree2_even = tree2_even[i];
        if (tree2_odd[i] > max_tree2_odd) max_tree2_odd = tree2_odd[i];
    }
    
    printf("[");
    for (int i = 0; i < n; i++) {
        if (i > 0) printf(",");
        printf("%d", tree1_even[i] + max_tree2_odd);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ Linear Space

8.5K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen