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.
- Difficulty: Hard
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^5edges1.length == n - 1edges2.length == m - 1edges1[i].length == edges2[i].length == 2the inputs are valid trees
Hints for Maximize the Number of Target Nodes After Connecting Trees II
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.
Hint 2
Inside the first tree, the targets of
iare the nodes with the same colour asi.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
- BFS the first tree from 0, colouring each node by depth parity, and count both colours.
- BFS the second tree the same way and take
best = max(count0, count1). 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 colJava
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)