3373: Maximize-the-Number-of-Target-Nodes-After-Connecting-Trees-II
Hard

Lowkey, this question does not seem toooooo hard.

Basically, for both graphs, we can iterate through all the nodes and colour each one red or blue such that no two neighbouring nodes share the same colour. - then, realise that to find all the nodes that are target to a chosen node, we just need to count the number of nodes that share the same colour as it

Knowing this, we just need to:

Finally, we can simply just return ans.

Code:

class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        vector<vector<int>> adjacencyArray1 (edges1.size()+1);
        vector<vector<int>> adjacencyArray2 (edges2.size()+1);

        for (vector<int>& edge : edges1) {
            adjacencyArray1[edge[0]].push_back(edge[1]);
            adjacencyArray1[edge[1]].push_back(edge[0]);
        }

        for (vector<int>& edge : edges2) {
            adjacencyArray2[edge[0]].push_back(edge[1]);
            adjacencyArray2[edge[1]].push_back(edge[0]);
        }

        vector<int> colour1 (edges1.size()+1, 0);

        vector<int> colour2 (edges2.size()+1, 0);
        queue<int> q;
        q.push(0);
        colour2[0] = 1;
        int majorityColour2 = 1;

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            
            for (int& adjacentNode : adjacencyArray2[node]) {
                if (colour2[adjacentNode] == 0) {
                    q.push(adjacentNode);
                    colour2[adjacentNode] = colour2[node] ^ 3;
                    if (colour2[adjacentNode] == 1) {
                        ++majorityColour2;
                    }
                }
            }
        }

        majorityColour2 = max(majorityColour2, (int)edges2.size()+1-majorityColour2);

        vector<int> ans ((int)edges1.size()+1, majorityColour2);
        q.push(0);
        colour1[0] = 1;

        int majorityColour1 = 1;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            
            for (int& adjacentNode : adjacencyArray1[node]) {
                if (colour1[adjacentNode] == 0) {
                    q.push(adjacentNode);
                    colour1[adjacentNode] = colour1[node] ^ 3;
                    if (colour1[adjacentNode] == 1) {
                        ++majorityColour1;
                    }
                }
            }
        }

        for (int i = 0; i < edges1.size()+1; ++i) {
            if (colour1[i] == 1) {
                ans[i] += majorityColour1;
            } else {
                ans[i] += (int)edges1.size()+1 - majorityColour1;
            }
        }
        return ans;
    }
};

Complexity:

Time Taken: