分类： leetcode

目标

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

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

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

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

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

示例 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]]
输出：[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 。

示例 2：

输入：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] = [ai, bi]
• 0 <= ai, bi < n
• edges2[i] = [ui, vi]
• 0 <= ui, vi < m
• 输入保证 edges1 和 edges2 都表示合法的树。

思路

有两棵树，当节点 a 与 b 之间的边数为偶数时，称 a 是 b 的目标节点，在两棵树任意节点之间连一条边，针对第一棵树的所有节点，计算其目标节点的最大个数。

与 3372.连接两棵树后最大目标节点数目I 相比，目标节点的条件从边数小于等于 k 变为了 偶数。

同一颗树中，某一个节点经过 偶数 或者 奇数条边到达的节点个数是固定的。不妨固定一个节点为根节点，经过 偶数 条边到达的节点集合为 A，经过 奇数 条边到达的节点集合为 B。集合 A 中节点的目标节点还是 A 中的节点，同理 B 中节点的目标节点还是 B 中的节点。

因此问题转化为计算两棵树的集合 A B，判断第一颗树的节点所属集合，如果属于 A，则取 A1 + Math.max(A2, B2)，否则取 B1 + Math.max(A2, B2)。

核心点是固定一个参考节点，根据到达该节点的边数将节点分类，可以快速计算出目标节点个数，如果针对每一节点暴力搜索目标节点个数肯定会超时。

代码

/**
 * @date 2025-05-29 23:50
 */
public class MaxTargetNodes3373 {

    public int[] maxTargetNodes(int[][] edges1, int[][] edges2) {
        int n = edges1.length + 1;
        int m = edges2.length + 1;
        List<Integer>[] g1 = new List[n];
        List<Integer>[] g2 = new List[m];
        Arrays.setAll(g1, x -> new ArrayList<>());
        Arrays.setAll(g2, x -> new ArrayList<>());
        for (int[] edge : edges1) {
            int a = edge[0];
            int b = edge[1];
            g1[a].add(b);
            g1[b].add(a);
        }
        for (int[] edge : edges2) {
            int a = edge[0];
            int b = edge[1];
            g2[a].add(b);
            g2[b].add(a);
        }
        Set<Integer>[] set1 = new HashSet[2];
        Arrays.setAll(set1, x -> new HashSet<>());
        int[] set2 = new int[]{0, 0};
        dfs(0, -1, g1, 0, set1);
        dfs(0, -1, g2, 0, set2);
        int max2 = Math.max(set2[0], set2[1]);
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            if (set1[0].contains(i)) {
                res[i] = set1[0].size() + max2;
            } else {
                res[i] = set1[1].size() + max2;
            }
        }
        return res;
    }

    public void dfs(int cur, int parent, List<Integer>[] g, int flag, Set<Integer>[] set) {
        set[flag].add(cur);
        for (Integer next : g[cur]) {
            if (next == parent) {
                continue;
            }
            dfs(next, cur, g, flag ^ 1, set);
        }
    }

    public void dfs(int cur, int parent, List<Integer>[] g, int flag, int[] res) {
        res[flag]++;
        for (Integer next : g[cur]) {
            if (next == parent) {
                continue;
            }
            dfs(next, cur, g, flag ^ 1, res);
        }
    }
}

性能