Maximize the Number of Target Nodes After Connecting Trees I
Problem
You have two undirected trees: the first with n nodes (edges edges1) and the second with m nodes (edges edges2). A node u is target to v when the path between them has at most k edges (a node is always target to itself).
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.
The best move is fixed: count the nodes within distance k of i inside tree 1, then attach i to the tree-2 node whose ball of radius k−1 is largest. So answer[i] = within1(i, k) + maxv within2(v, k−1).
edges1 = [[0,1],[0,2],[2,3],[2,4]], edges2 = [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]], k = 2[9,7,9,8,8]def maxTargetNodes(edges1, edges2, k):
def build(edges): # adjacency list + node count
n = len(edges) + 1
g = [[] for _ in range(n)]
for a, b in edges:
g[a].append(b)
g[b].append(a)
return g, n
def reachable(g, n, src, limit): # nodes within distance <= limit
if limit < 0:
return 0
seen = [False] * n
seen[src] = True
q = deque([(src, 0)])
cnt = 1
while q:
node, d = q.popleft()
if d == limit: # ball edge: do not expand
continue
for nb in g[node]:
if not seen[nb]:
seen[nb] = True
cnt += 1
q.append((nb, d + 1))
return cnt
g1, n = build(edges1)
g2, m = build(edges2)
best2 = 0 # best tree-2 anchor (radius k-1)
for v in range(m):
best2 = max(best2, reachable(g2, m, v, k - 1))
ans = []
for i in range(n): # tree-1 ball (radius k) + best2
ans.append(reachable(g1, n, i, k) + best2)
return ansfunction maxTargetNodes(edges1, edges2, k) {
function build(edges) { // adjacency list + node count
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);
}
return [g, n];
}
function reachable(g, n, src, limit) { // nodes within distance <= limit
if (limit < 0) return 0;
const seen = new Array(n).fill(false);
seen[src] = true;
const q = [[src, 0]];
let cnt = 1;
for (let h = 0; h < q.length; h++) {
const [node, d] = q[h];
if (d === limit) continue; // ball edge: do not expand
for (const nb of g[node]) {
if (!seen[nb]) {
seen[nb] = true;
cnt++;
q.push([nb, d + 1]);
}
}
}
return cnt;
}
const [g1, n] = build(edges1);
const [g2, m] = build(edges2);
let best2 = 0; // best tree-2 anchor (radius k-1)
for (let v = 0; v < m; v++) {
best2 = Math.max(best2, reachable(g2, m, v, k - 1));
}
const ans = [];
for (let i = 0; i < n; i++) { // tree-1 ball (radius k) + best2
ans.push(reachable(g1, n, i, k) + best2);
}
return ans;
}int[] maxTargetNodes(int[][] edges1, int[][] edges2, int k) {
List<List<Integer>> g1 = build(edges1); // adjacency lists
List<List<Integer>> g2 = build(edges2);
int n = g1.size(), m = g2.size();
int best2 = 0; // best tree-2 anchor (radius k-1)
for (int v = 0; v < m; v++) {
best2 = Math.max(best2, reachable(g2, v, k - 1));
}
int[] ans = new int[n];
for (int i = 0; i < n; i++) { // tree-1 ball (radius k) + best2
ans[i] = reachable(g1, i, k) + best2;
}
return ans;
}
List<List<Integer>> build(int[][] edges) {
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]); }
return g;
}
int reachable(List<List<Integer>> g, int src, int limit) {
if (limit < 0) return 0;
int n = g.size();
boolean[] seen = new boolean[n];
seen[src] = true;
Deque<int[]> q = new ArrayDeque<>();
q.add(new int[]{src, 0});
int cnt = 1;
while (!q.isEmpty()) {
int[] cur = q.poll();
if (cur[1] == limit) continue; // ball edge: do not expand
for (int nb : g.get(cur[0])) {
if (!seen[nb]) {
seen[nb] = true;
cnt++;
q.add(new int[]{nb, cur[1] + 1});
}
}
}
return cnt;
}vector<int> maxTargetNodes(vector<vector<int>>& edges1,
vector<vector<int>>& edges2, int k) {
auto build = [](vector<vector<int>>& edges) { // adjacency list
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]); }
return g;
};
auto reachable = [](vector<vector<int>>& g, int src, int limit) {
if (limit < 0) return 0;
int n = g.size();
vector<char> seen(n, 0);
seen[src] = 1;
queue<pair<int,int>> q;
q.push({src, 0});
int cnt = 1;
while (!q.empty()) {
auto [node, d] = q.front(); q.pop();
if (d == limit) continue; // ball edge: do not expand
for (int nb : g[node]) {
if (!seen[nb]) {
seen[nb] = 1;
cnt++;
q.push({nb, d + 1});
}
}
}
return cnt;
};
vector<vector<int>> g1 = build(edges1), g2 = build(edges2);
int n = g1.size(), m = g2.size();
int best2 = 0; // best tree-2 anchor (k-1)
for (int v = 0; v < m; v++)
best2 = max(best2, reachable(g2, v, k - 1));
vector<int> ans(n);
for (int i = 0; i < n; i++) // tree-1 ball (k) + best2
ans[i] = reachable(g1, i, k) + best2;
return ans;
}Explanation
Adding one edge from a tree-1 node i to a tree-2 node v simply glues the two trees at that single point. Everything target to i is then: every tree-1 node within distance k of i (unchanged by the new edge), plus the tree-2 nodes you can reach. To reach a tree-2 node you must first spend one edge crossing the bridge into v, so only tree-2 nodes within distance k−1 of v count.
The two halves are independent. The tree-1 part depends only on i; the tree-2 part depends only on which anchor v we choose. To maximise the total we just pick the single best anchor — the tree-2 node whose radius-(k−1) ball contains the most nodes. Call that count best2; it is the same constant for every i.
So the algorithm is two independent passes of a bounded breadth-first search. reachable(g, src, limit) runs a BFS from src that stops expanding once a node sits at distance limit, returning how many nodes lie within the ball. We compute best2 = max over all tree-2 nodes with limit = k−1, then for each tree-1 node i we return reachable(g1, i, k) + best2.
The single edge case worth remembering is k = 0: then k−1 = −1, the ball is empty, and reachable returns 0 — you cannot even reach the anchor itself, so best2 = 0 and every answer is just 1 (the node itself in tree 1).
For the sample, the best tree-2 anchor reaches 4 nodes within distance 1. Tree-1 balls of radius 2 hold [5, 3, 5, 4, 4] nodes, and adding best2 = 4 gives the output [9, 7, 9, 8, 8].