Maximize the Number of Target Nodes After Connecting Trees II
Problem
You have two undirected trees: the first with n nodes (edges edges1) and the second with m nodes (edges edges2). Node u is target to v when the path between them has an even number of edges (a node is always target to itself, distance 0).
For every node i of the first tree you may add one edge from i to any node of the second tree (each query is independent). Return answer[i], the maximum number of nodes target to i.
A tree is bipartite: 2-color it so neighbors differ. Two nodes are at even distance exactly when they share a color. So inside tree 1, the even-distance nodes from i are exactly those of i's color. Crossing the new edge flips parity, so the best tree-2 contribution is its larger color class. Thus answer[i] = same1(i) + max(odd2, even2).
edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]][8,7,7,8,8]def maxTargetNodes(edges1, edges2):
def color(edges): # 2-color the tree by BFS parity
n = len(edges) + 1
g = [[] for _ in range(n)]
for a, b in edges:
g[a].append(b)
g[b].append(a)
col = [-1] * n
col[0] = 0
cnt = [1, 0] # nodes of color 0 / color 1
q = deque([0])
while q:
u = q.popleft()
for v in g[u]:
if col[v] == -1:
col[v] = col[u] ^ 1 # neighbor gets opposite color
cnt[col[v]] += 1
q.append(v)
return col, cnt
col1, cnt1 = color(edges1)
_, cnt2 = color(edges2)
best2 = max(cnt2) # larger color class of tree 2
ans = []
for i in range(len(col1)): # same color = even distance from i
ans.append(cnt1[col1[i]] + best2)
return ansfunction maxTargetNodes(edges1, edges2) {
function color(edges) { // 2-color the tree by BFS parity
const n = edges.length + 1;
const g = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
g[a].push(b);
g[b].push(a);
}
const col = new Array(n).fill(-1);
col[0] = 0;
const cnt = [1, 0]; // nodes of color 0 / color 1
const q = [0];
for (let h = 0; h < q.length; h++) {
const u = q[h];
for (const v of g[u]) {
if (col[v] === -1) {
col[v] = col[u] ^ 1; // neighbor gets opposite color
cnt[col[v]]++;
q.push(v);
}
}
}
return { col, cnt };
}
const t1 = color(edges1);
const t2 = color(edges2);
const best2 = Math.max(t2.cnt[0], t2.cnt[1]); // larger color class of tree 2
const ans = [];
for (let i = 0; i < t1.col.length; i++) { // same color = even distance
ans.push(t1.cnt[t1.col[i]] + best2);
}
return ans;
}int[] maxTargetNodes(int[][] edges1, int[][] edges2) {
int[] col1 = new int[edges1.length + 1];
int[] cnt1 = color(edges1, col1); // 2-color tree 1, fill col1
int[] cnt2 = color(edges2, new int[edges2.length + 1]);
int best2 = Math.max(cnt2[0], cnt2[1]); // larger color class of tree 2
int[] ans = new int[col1.length];
for (int i = 0; i < col1.length; i++) { // same color = even distance
ans[i] = cnt1[col1[i]] + best2;
}
return ans;
}
int[] color(int[][] edges, int[] col) {
int n = edges.length + 1;
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < n; i++) g.add(new ArrayList<>());
for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
Arrays.fill(col, -1);
col[0] = 0;
int[] cnt = {1, 0}; // nodes of color 0 / color 1
Deque<Integer> q = new ArrayDeque<>();
q.add(0);
while (!q.isEmpty()) {
int u = q.poll();
for (int v : g.get(u)) {
if (col[v] == -1) {
col[v] = col[u] ^ 1; // neighbor gets opposite color
cnt[col[v]]++;
q.add(v);
}
}
}
return cnt;
}vector<int> maxTargetNodes(vector<vector<int>>& edges1,
vector<vector<int>>& edges2) {
auto color = [](vector<vector<int>>& edges, vector<int>& col) {
int n = edges.size() + 1;
vector<vector<int>> g(n);
for (auto& e : edges) { g[e[0]].push_back(e[1]); g[e[1]].push_back(e[0]); }
col.assign(n, -1);
col[0] = 0;
array<int,2> cnt = {1, 0}; // color 0 / color 1 counts
queue<int> q;
q.push(0);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (col[v] == -1) {
col[v] = col[u] ^ 1; // opposite color
cnt[col[v]]++;
q.push(v);
}
}
}
return cnt;
};
vector<int> col1, col2;
auto cnt1 = color(edges1, col1);
auto cnt2 = color(edges2, col2);
int best2 = max(cnt2[0], cnt2[1]); // larger color class
vector<int> ans(col1.size());
for (int i = 0; i < (int)col1.size(); i++) // same color = even distance
ans[i] = cnt1[col1[i]] + best2;
return ans;
}Explanation
"Target" here means the path length is even. Every tree is bipartite, so we can 2-color it such that adjacent nodes always differ. Walking one edge flips the color; walking an even number of edges returns to the same color. Therefore two nodes lie at an even distance precisely when they share a color. Inside tree 1, the nodes target to i are exactly the nodes of i's own color — a constant that depends only on which color i has.
Now add one edge from tree-1 node i to tree-2 node v. That bridge is a single edge, so to reach a tree-2 node we cross it once (parity flip) and then walk inside tree 2. A tree-2 node is target to i when the total path length is even, which happens for exactly one of the two tree-2 colors relative to v. By choosing v freely we can always line up the larger color class of tree 2. So the tree-2 contribution is the constant best2 = max(even, odd), independent of i.
The algorithm is two BFS colorings. For each tree we sweep from node 0, paint neighbors the opposite color, and tally cnt[0] and cnt[1]. From tree 2 we keep only best2 = max(cnt2). From tree 1 we keep the per-color counts cnt1 and each node's color col1[i].
The final answer is one pass: answer[i] = cnt1[col1[i]] + best2. Both colorings are linear, so the whole solution runs in O(n + m) time — essential given n, m up to 105. Unlike the "I" version there is no radius k; parity makes the per-node counts collapse to just two values.
For the sample, tree 2 colors into classes of size 3 and 5, so best2 = 5. In tree 1, node 0 is color 0; its neighbors 1 and 2 are color 1, and 2's children 3, 4 are color 0. So color-0 = {0, 3, 4} (size 3) and color-1 = {1, 2} (size 2), giving cnt1 = [3, 2]. Each node adds best2 = 5 to its color count: nodes 0, 3, 4 get 3 + 5 = 8 and nodes 1, 2 get 2 + 5 = 7, so answer = [8, 7, 7, 8, 8].