题目描述

有两棵 无向 树，分别有 n 和 m 个树节点。两棵树中的节点编号分别为 [0, n - 1] 和 [0, m - 1] 中的整数。

给你两个二维整数 edges1 和 edges2，长度分别为 n - 1 和 m - 1，其中 edges1[i] = [a_i, b_i] 表示第一棵树中节点 a_i和 b_i 之间有一条边，edges2[i] = [u_i, v_i] 表示第二棵树中节点 u_i 和 v_i 之间有一条边。

如果节点 u 和节点 v 之间路径的边数是偶数，那么我们称节点 u 是节点 v 的 目标节点。注意，一个节点一定是它自己的 目标节点。

请你返回一个长度为 n 的整数数组 answer，answer[i] 表示将第一棵树中的一个节点与第二棵树中的一个节点连接一条边后，第一棵树中节点 i 的 目标节点 数目的 最大值。

注意，每个查询相互独立。意味着进行下一次查询之前，你需要先把刚添加的边给删掉。

样例

输入：
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]

解释：

对于 i = 0，连接第一棵树中的节点 0 和第二棵树中的节点 0。
对于 i = 1，连接第一棵树中的节点 1 和第二棵树中的节点 4。
对于 i = 2，连接第一棵树中的节点 2 和第二棵树中的节点 7。
对于 i = 3，连接第一棵树中的节点 3 和第二棵树中的节点 0。
对于 i = 4，连接第一棵树中的节点 4 和第二棵树中的节点 4。

输入：
edges1 = [[0,1],[0,2],[0,3],[0,4]]
edges2 = [[0,1],[1,2],[2,3]]

输出：[3,6,6,6,6]

解释：

对于每个 i，连接第一棵树中的节点 i 和第二棵树中的任意一个节点。

限制

• 2 <= n, m <= 10^5
• edges1.length == n - 1
• edges2.length == m - 1
• edges1[i].length == edges2[i].length == 2
• edges1[i] = [a_i, b_i]
• 0 <= a_i, b_i < n
• edges2[i] = [u_i, v_i]
• 0 <= u_i, v_i < m
• 输入保证 edges1 和 edges2 都表示合法的树。

算法

(思维题，黑白染色，宽度优先遍历) $O(n + m)$

1. 分别对两棵树的节点进行黑白染色，染色的目的是可以快速求出路径边数为偶数的节点个数。
2. 在同一棵树中，相同颜色的节点之间路径的边数一定是偶数。
3. 对于每个查询节点 $i$，先求出当前树中偶数边的节点数，然后去找第二棵树中的某个黑色点或者白色点，可以得到第二棵树中所有白色或者黑色点的节点。

时间复杂度

• 分别从任意节点开始宽度优先遍历两棵树一次，故时间复杂度为 $O(n + m)$。
• 枚举答案的时间复杂度为 $O(n)$。
• 故总时间复杂度为 $O(n + m)$。

空间复杂度

• 需要 $O(n + m)$ 的额外空间存储宽度优先遍历的队列和颜色数组。

C++ 代码

class Solution {
private:
    queue<int> q;

    void bfs(const vector<vector<int>> &graph, vector<int> &col) {
        const int n = graph.size();
        col[0] = 0;

        q.push(0);
        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : graph[u]) {
                if (col[v] != -1)
                    continue;

                col[v] = 1 - col[u];
                q.push(v);
            }
        }
    }

public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1,
        vector<vector<int>>& edges2
    ) {
        const int n1 = edges1.size() + 1;
        const int n2 = edges2.size() + 1;

        vector<vector<int>> graph1(n1);
        vector<vector<int>> graph2(n2);

        for (const auto &e : edges1) {
            graph1[e[0]].push_back(e[1]);
            graph1[e[1]].push_back(e[0]);
        }

        for (const auto &e : edges2) {
            graph2[e[0]].push_back(e[1]);
            graph2[e[1]].push_back(e[0]);
        }

        vector<int> col1(n1, -1), col2(n2, -1);
        bfs(graph1, col1);
        bfs(graph2, col2);

        int o1 = 0, o2 = 0;
        for (int i = 0; i < n1; i++)
            if (col1[i] == 0)
                ++o1;

        for (int i = 0; i < n2; i++)
            if (col2[i] == 0)
                ++o2;

        int ma = max(o2, n2 - o2);

        vector<int> ans(n1);
        for (int i = 0; i < n1; i++)
            ans[i] = (col1[i] == 0 ? o1 : n1 - o1) + ma;

        return ans;
    }
};