Maximize the Number of Target Nodes After Connecting Trees II

Hard
1729.

Maximize the Number of Target Nodes After Connecting Trees II

Maximize the Number of Target Nodes After Connecting Trees II is a hard coding problem on depth-first search, breadth-first search and trees, asked in Amazon and Google interviews.

There are two undirected trees: the first has n nodes labelled 0 to n - 1 with edges edges1, the second has m nodes labelled 0 to m - 1 with edges edges2.

Node u is a target of node v if the path between them has an even number of edges. A node is always a target of itself (zero edges).

For every node i of the first tree, you may add one edge joining any node of the first tree to any node of the second tree, and then count the targets of i in the combined tree. Each i is answered independently — the added edge is removed before the next one.

Return an array answer of length n where answer[i] is the maximum possible number of targets of node i.

Example 1

Input
edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]
Output
[8,7,7,8,8]
Explanation
Node 0 has the even-distance nodes 0, 3 and 4 in its own tree; the best attachment adds 5 nodes of the second tree.

Example 2

Input
edges1 = [[0,1],[0,2],[0,3],[0,4]], edges2 = [[0,1],[1,2],[2,3]]
Output
[3,6,6,6,6]

Example 3

Input
edges1 = [[0,1]], edges2 = [[0,1]]
Output
[2,2]
Explanation
Each node is its own target, and attaching it to one node of the second tree reaches the other at distance 2.

Constraints

  • 2 <= n, m <= 10^5
  • edges1.length == n - 1
  • edges2.length == m - 1
  • edges1[i].length == edges2[i].length == 2
  • the inputs are valid trees
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} edges1
 * @param {number[][]} edges2
 * @return {number[]}
 */
var maxTargetNodes = function(edges1, edges2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximize the Number of Target Nodes After Connecting Trees II Solution

Maximize the Number of Target Nodes After Connecting Trees II solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximize the Number of Target Nodes After Connecting Trees II is a hard coding problem on depth-first search, breadth-first search and trees, asked in Amazon and Google interviews.

Problem statement

There are two undirected trees: the first has n nodes labelled 0 to n - 1 with edges edges1, the second has m nodes labelled 0 to m - 1 with edges edges2.

Node u is a target of node v if the path between them has an even number of edges. A node is always a target of itself (zero edges).

For every node i of the first tree, you may add one edge joining any node of the first tree to any node of the second tree, and then count the targets of i in the combined tree. Each i is answered independently — the added edge is removed before the next one.

Return an array answer of length n where answer[i] is the maximum possible number of targets of node i.

Example 1

Input: edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]
Output: [8,7,7,8,8]
Explanation: Node 0 has the even-distance nodes 0, 3 and 4 in its own tree; the best attachment adds 5 nodes of the second tree.

Example 2

Input: edges1 = [[0,1],[0,2],[0,3],[0,4]], edges2 = [[0,1],[1,2],[2,3]]
Output: [3,6,6,6,6]

Example 3

Input: edges1 = [[0,1]], edges2 = [[0,1]]
Output: [2,2]
Explanation: Each node is its own target, and attaching it to one node of the second tree reaches the other at distance 2.

Constraints

  • 2 <= n, m <= 10^5
  • edges1.length == n - 1
  • edges2.length == m - 1
  • edges1[i].length == edges2[i].length == 2
  • the inputs are valid trees

Hints for Maximize the Number of Target Nodes After Connecting Trees II

  1. Hint 1

    In a tree, the distance between two nodes is even exactly when their depths have the same parity. So 2-colour each tree by depth parity.

  2. Hint 2

    Inside the first tree, the targets of i are the nodes with the same colour as i.

  3. Hint 3

    Every path into the second tree crosses the new edge, which flips parity. Choosing the endpoint's colour well, you can always collect the larger colour class of the second tree: answer[i] = |colour class of i| + max(class sizes of tree 2).

How to solve Maximize the Number of Target Nodes After Connecting Trees II

Parity of a tree path equals the parity of the difference of the two depths, so a 2-colouring answers every "even distance" question at once. The second tree contributes its larger colour class regardless of i.

Approach

  1. BFS the first tree from 0, colouring each node by depth parity, and count both colours.
  2. BFS the second tree the same way and take best = max(count0, count1).
  3. answer[i] = count1[colour of i] + best.

Why it works

Two nodes of one tree are at even distance iff they share a colour. A path from i into the second tree goes from i to the attachment point a, across the new edge to b, then to w. Attaching at a = i costs nothing, and the parity of the total is 1 + dist(b, w), so the targets are the nodes coloured opposite to b. Picking b in the smaller class hands you the larger one, and no choice can do better.

Complexity

  • Time — O(n + m)
  • Space — O(n + m)

Pitfalls

  • Running a BFS from every node is O(n²), too slow for 10^5 — the colour classes answer everything.
  • The new edge adds one to every path into the second tree, so the endpoint itself is at odd distance.
  • A node is its own target: count it in its colour class.

Reference solution

Python

from typing import List

def maxTargetNodes(edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:
    c2 = _colour(edges2)
    ones = sum(c2)
    best = max(ones, len(c2) - ones)
    c1 = _colour(edges1)
    cnt = [len(c1) - sum(c1), sum(c1)]
    return [cnt[c] + best for c in c1]

def _colour(edges: List[List[int]]) -> List[int]:
    n = len(edges) + 1
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    col = [-1] * n
    col[0] = 0
    q = [0]
    for u in q:
        for v in adj[u]:
            if col[v] < 0:
                col[v] = col[u] ^ 1
                q.append(v)
    return col

Java

static int[] colour(int[][] edges) {
    int n = edges.length + 1;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
    int[] col = new int[n], q = new int[n];
    Arrays.fill(col, -1);
    col[0] = 0;
    int tail = 0;
    q[tail++] = 0;
    for (int h = 0; h < tail; h++) {
        int u = q[h];
        for (int v : adj.get(u)) if (col[v] < 0) { col[v] = col[u] ^ 1; q[tail++] = v; }
    }
    return col;
}

public static int[] maxTargetNodes(int[][] edges1, int[][] edges2) {
    int[] c2 = colour(edges2);
    int ones = 0;
    for (int c : c2) ones += c;
    int best = Math.max(ones, c2.length - ones);
    int[] c1 = colour(edges1);
    int[] cnt = new int[2];
    for (int c : c1) cnt[c]++;
    int[] ans = new int[c1.length];
    for (int i = 0; i < c1.length; i++) ans[i] = cnt[c1[i]] + best;
    return ans;
}

C++

vector<int> colour(vector<vector<int>>& edges) {
    int n = edges.size() + 1;
    vector<vector<int>> adj(n);
    for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    vector<int> col(n, -1), q;
    col[0] = 0;
    q.push_back(0);
    for (size_t h = 0; h < q.size(); h++) {
        int u = q[h];
        for (int v : adj[u]) if (col[v] < 0) { col[v] = col[u] ^ 1; q.push_back(v); }
    }
    return col;
}

vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
    vector<int> c2 = colour(edges2);
    int ones = 0;
    for (int c : c2) ones += c;
    int best = max(ones, (int) c2.size() - ones);
    vector<int> c1 = colour(edges1);
    int cnt[2] = {0, 0};
    for (int c : c1) cnt[c]++;
    vector<int> ans(c1.size());
    for (size_t i = 0; i < c1.size(); i++) ans[i] = cnt[c1[i]] + best;
    return ans;
}

JavaScript

var maxTargetNodes = function(edges1, edges2) {
    var c2 = colour(edges2), ones = 0;
    for (var i = 0; i < c2.length; i++) ones += c2[i];
    var best = Math.max(ones, c2.length - ones);
    var c1 = colour(edges1), cnt = [0, 0];
    for (var j = 0; j < c1.length; j++) cnt[c1[j]]++;
    var ans = [];
    for (var k = 0; k < c1.length; k++) ans.push(cnt[c1[k]] + best);
    return ans;
};

var colour = function(edges) {
    var n = edges.length + 1, adj = [], col = [];
    for (var i = 0; i < n; i++) { adj.push([]); col.push(-1); }
    for (var e = 0; e < edges.length; e++) {
        adj[edges[e][0]].push(edges[e][1]);
        adj[edges[e][1]].push(edges[e][0]);
    }
    col[0] = 0;
    var q = [0];
    for (var h = 0; h < q.length; h++) {
        var u = q[h];
        for (var j = 0; j < adj[u].length; j++) {
            var v = adj[u][j];
            if (col[v] < 0) { col[v] = col[u] ^ 1; q.push(v); }
        }
    }
    return col;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)