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 ther

maxTargetNodes.js

/**
 * Computes the maximum number of target nodes achievable.
 * 
 * @param {number[][]} edges1 - List of edges in the first graph.
 * @param {number[][]} edges2 - List of edges in the second graph.
 * @return {number[]} - Maximum number of target nodes for each node in graph1.
 */
var maxTargetNodes = function (edges1, edges2) {
    // Determine the highest numbered node in each graph
    let m = Math.max(...edges1.flat());
    let n = Math.max(...edges2.flat());

    // Create adjacency lists for both graphs
    let adj1 = Array.from({ length: m + 1 }, () => []);
    let adj2 = Array.from({ length: n + 1 }, () => []);

    // Populate adjacency lists
    for (let [u, v] of edges1) {
        adj1[u].push(v);
        adj1[v].push(u);
    }
    for (let [u, v] of edges2) {
        adj2[u].push(v);
        adj2[v].push(u);
    }

    const colorGraph = (adj) => {
        let queue = [[0, true]]; // Start with node 0, colored as white (true)
        let white = 0, black = 0;
        let colorArr = new Array(adj.length);
        let visited = new Array(adj.length).fill(false);
        visited[0] = true;

        while (queue.length) {
            let [node, currColor] = queue.shift();
            colorArr[node] = currColor;
            if (currColor) white++;
            else black++;

            // Traverse neighbors
            for (let neighbor of adj[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.push([neighbor, !currColor]); // Alternate colors
                }
            }
        }
        return [white, black, colorArr];
    };

    // Get color distributions for both graphs
    let [white1, black1, colorArr1] = colorGraph(adj1);
    let [white2, black2] = colorGraph(adj2);

    let result = [];

    // Compute maximum target nodes for each node
    for (let i = 0; i <= m; i++) {
        let maxGroupSize = Math.max(white2, black2);
        result.push(colorArr1[i] ? white1 + maxGroupSize : black1 + maxGroupSize);
    }

    return result;
};