点击获取AI摘要

3373. 连接两棵树后最大目标节点数目 II H

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

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

如果节点 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 。

示例1

示例 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

提示：

  • 2 <= n, m <= 10⁵
  • edges1.length == n - 1
  • edges2.length == m - 1
  • edges1[i].length == edges2[i].length == 2
  • edges1[i] = [ai, bi]
  • 0 <= aᵢ, bᵢ < n
  • edges2[i] = [uᵢ, vᵢ]
  • 0 <= uᵢ, vᵢ < m
  • 输入保证 edges1 和 edges2 都表示合法的树。

问题分析

  • 题目给出两棵无向树，分别记作树1（节点数为 n，编号 0…n-1，边集 edges1）和树2（节点数为 m，编号 0…m-1，边集 edges2）。

  • 定义：若节点 u 和节点 v 之间路径上的边数是偶数，则称 u 是 v 的“目标节点”（目标关系是对称的；距离为 0 时，节点自己也是自己的目标节点）。

  • 对于树1中的每个节点 i ，我们可以“在树1的 i 和树2的某个节点 j 之间额外连一条边”，这样相当于把两棵树连成一棵大树。连边以后，在这棵大树中，节点 i 与其它所有节点（既包括树1中的节点，也包括树2中的节点）的距离都确定了，我们希望计算“有多少个节点与 i 的距离为偶数”——即 i 在新大树中的目标节点数目。

  • 题目要求对 树1 中的每个 i ，都可以选择一个不同的 j 来连边（每个 i 是一种“独立”的查询，连边结束后会删掉，互不影响），求出当选择最优的 j 时，节点 i 能得到的最大目标节点数。

算法思路

  1. 拆解距离关系

    • 对树1内部的任意两个节点 i 和 x ，它们的距离是否为偶数，与“它们在某个根节点下的颜色（奇偶深度）”有关。实际上，可以把任意一棵树看成二分图：对树1，任选一个根（如 0），做 BFS 打标“深度奇偶”。记 col1[u]=0/1 表示节点 u 到根 0 的距离 mod 2；同理树2记 col2[v]。

    • 在同一个树内部，对于树1 的任意 i 和 x ，dist_tree1(i,x)%2 == (col1[i] xor col1[x])。若结果为 0 ，则距离为偶数；若为 1 ，则距离为奇数。

    • 连接边后，新大树中：

      • 树1 中的 x 到 i 的距离保持原来的关系，仍然是 dist_tree1(i,x)；
      • 树2 中的 y 到 i 的距离变为 dist_tree1(i, j) + 1 + dist_tree2(j, y)，其中 j 是我们连接的“接口”节点。在树1里，从 i 到 j 若 i==j 时 dist=0，否则它完全在树1内的路径；但是题目每次都只连“树1的 i 到树2的 j”这一条边，所以在树1内部，dist_tree1(i,j) 恰好等于 0 当且仅当 i=j，否则这条树内路径我们 并不实际连除 i=j 外的其它； 更严谨地，连边规则是“在 i 和 j 之间连一条新边”，无论 i 是否在树1里有到 j 的路径（当然 j 不在树1），“树1内部”还是原来的那棵树：
        • 树1→树1：dist_large(i,x) = dist_tree1(i,x)。
        • 树1→树2：dist_large(i,y) = 1 + dist_tree2(j,y)。
          （因为在大图中，i→j 只有 1 条新边，树1里 i→j 不存在原路径——跨树；树2 里 j→y 路径和原一致。）

    • 因此，在大树里：

      • 对于树1 内部某个 x，dist_large(i,x)%2 == dist_tree1(i,x)%2 == (col1[i] xor col1[x])。
        当 (col1[i] xor col1[x])==0 时，x 是 i 的“目标”。

      • 对于树2 内部某个 y，dist_large(i,y)%2 == (1 + dist_tree2(j,y))%2 == 1 xor (col2[j] xor col2[y])。
        令 d2_parity = (col2[j] xor col2[y])，若 d2_parity==0（即 j,y 在树2里同偶数深度标记） 则 1 xor 0 = 1（距离奇数），若 d2_parity==1 则 1 xor 1 = 0（距离偶数）。
        我们希望大距离为偶数，也就是：

        1⊕(col2[j]⊕col2[y])=0⇔(col2[j]⊕col2[y])=1⇔col2[j]≠col2[y]1 \oplus (\text{col2}[j] \oplus \text{col2}[y]) = 0 \quad \Leftrightarrow \quad (\text{col2}[j] \oplus \text{col2}[y]) = 1 \quad \Leftrightarrow \quad \text{col2}[j] \neq \text{col2}[y]

        换言之，在树2 中，仅有与 j 在“二分染色”中“异色”的节点 y 才会和 i 形成“偶数距离”。

  2. 把计数分为两部分相加

    • 树1 内部：对于固定的 i，树1 里与 i 距离为偶数的节点个数，只与 col1[i] 有关；因为只要 col1[x] == col1[i]，它们在树1 里距离就是偶数。令

      cnt1_0=∣{u∈树1:col1[u]=0}∣,cnt1_1=∣{u∈树1:col1[u]=1}∣\mathrm{cnt1\_0} = \left| \{ u \in \text{树1} : \text{col1}[u] = 0 \} \right|, \quad \mathrm{cnt1\_1} = \left| \{ u \in \text{树1} : \text{col1}[u] = 1 \} \right|

      若 col1[i]==0，则树1 内部与 i “偶数距离”的节点数 = cnt1_0；若 col1[i]==1，则为 cnt1_1。

    • 树2 部分：若我们把树1 的 i 连到树2 的 j ，那么在大树里，任何树2 内部的节点 y 只要 col2[y] ≠ col2[j]，它就与 i “偶数距离”。
      因此，定义树2 中：

      cnt2_0=∣{v∈树2:col2[v]=0}∣,cnt2_1=∣{v∈树2:col2[v]=1}∣\mathrm{cnt2\_0} = \left| \{ v \in \text{树2} : \text{col2}[v] = 0 \} \right|, \quad \mathrm{cnt2\_1} = \left| \{ v \in \text{树2} : \text{col2}[v] = 1 \} \right|

      若 col2[j]==0，则与 j 异色的节点数是 cnt2_1；若 col2[j]==1，则异色的节点数是 cnt2_0。
      所以对于固定的 j，树2 中与 j 距离为奇（col2[j] xor col2[y]==1） 的节点数 = 若 col2[j]==0 → cnt2_1；若 col2[j]==1 → cnt2_0。这部分正好是连上 i 以后，能贡献给 i “偶数距离”的树2 节点数。

  3. 两个部分相加后再最大化

    • 对于树1 中的节点 i，选择某个 j 来连边，那么“大树中与 i 偶数距离的节点数” =

      1
      2
      （树1 内部与 i 距离偶数的节点数） + （树2 内部与 j 距离奇数的节点数）
      = （col1[i]==0 ? cnt1_0 : cnt1_1） + （col2[j]==0 ? cnt2_1 : cnt2_0）.

    • 第一项只与 i 在树1 中的深度奇偶（col1[i]）相关，第二项只与 j 在树2 中的深度奇偶（col2[j]）相关。它们是“加法分离”的，互不影响。

    • 因此，若我们要对 i 单独做一次“独立查询”来最大化这个和，就只需要把 j 选成能让 （col2[j]==0 ? cnt2_1 : cnt2_0） 最大化的那个颜色：

      • 若 cnt2_0 >= cnt2_1，那么只要选一个 col2[j]==1 的 j，就能得到树2 贡献 cnt2_0。
      • 否则就选一个 col2[j]==0 的 j ，得到树2 贡献 cnt2_1。

    • 这样，不论 i 是哪个，都应该“二分染色完树2 以后”取

      1
      best2 = max(cnt2_0, cnt2_1).

    • 最终对每个 i ：

      1
      answer[i] = （col1[i]==0 ? cnt1_0 : cnt1_1） + best2.

由此可知，这个问题的难点并不在于对每个 i 枚举 m 个 j，而是在于利用“树的二分染色”将「偶数距离」的计数化归到“同色/异色”的简单计数上，整体复杂度只需 O(n+m)O(n+m)。

时间复杂度

时间复杂度

  • 构建邻接表：O(n+m)O(n + m)（n=树1节点数，m=树2节点数）。
  • BFS 染色（树1 + 树2）：O(n+m)O(n + m)。
  • 最后生成答案：O(n)O(n)。
    总体：O(n+m)O(n + m)，空间复杂度也是 O(n+m)O(n + m) 来存储邻接表和标记数组。

代码分解

1. 对树1 做 BFS/DFS 二分染色

  • 任意定根（通常选 0），对整棵树1 做 BFS，生成一个 col1[0..n-1]，其中 col1[u] = 深度(u)%2。同时统计 cnt1_0、cnt1_1（即染色后两个集合大小）。

2. 对树2 做同样的 BFS/DFS 二分染色

  • 任选根（如 0），对树2 做 BFS，得到 col2[0..m-1]，统计 cnt2_0、cnt2_1。

3. 令 best2 = max(cnt2_0, cnt2_1)，这是树2 在“连边后能给 i 捐献的最大“偶数距离”节点数”。

4. 对树1 的每个 i ：

1
2
3
4
if col1[i] == 0:
    answer[i] = cnt1_0 + best2
else:
    answer[i] = cnt1_1 + best2

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
from collections import deque
from typing import List

class Solution:
    def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:

        # 树1 的节点数 n = len(edges1) + 1
        n = len(edges1) + 1
        # 树2 的节点数 m = len(edges2) + 1
        m = len(edges2) + 1

        # —— 步骤 1：对树1 做二分染色 —— 
        adj1 = [[] for _ in range(n)]
        for u, v in edges1:
            adj1[u].append(v)
            adj1[v].append(u)

        col1 = [-1] * n   # col1[i] = 0 or 1 ，表示 i 的深度 % 2
        cnt1_0 = 0
        cnt1_1 = 0

        # BFS 从节点 0 开始
        queue = deque([0])
        col1[0] = 0
        cnt1_0 += 1
        while queue:
            u = queue.popleft()
            for w in adj1[u]:
                if col1[w] == -1:
                    col1[w] = col1[u] ^ 1
                    if col1[w] == 0:
                        cnt1_0 += 1
                    else:
                        cnt1_1 += 1
                    queue.append(w)
        # —— 步骤 1 完成 —— 

        # —— 步骤 2：对树2 做二分染色 —— 
        adj2 = [[] for _ in range(m)]
        for u, v in edges2:
            adj2[u].append(v)
            adj2[v].append(u)

        col2 = [-1] * m
        cnt2_0 = 0
        cnt2_1 = 0

        queue = deque([0])
        col2[0] = 0
        cnt2_0 += 1
        while queue:
            u = queue.popleft()
            for w in adj2[u]:
                if col2[w] == -1:
                    col2[w] = col2[u] ^ 1
                    if col2[w] == 0:
                        cnt2_0 += 1
                    else:
                        cnt2_1 += 1
                    queue.append(w)
        # —— 步骤 2 完成 —— 

        # —— 步骤 3：计算树2 可以贡献的最大“偶数距离”节点数 —— 
        best2 = max(cnt2_0, cnt2_1)

        # —— 步骤 4：对树1 每个 i，直接加上 best2 —— 
        answer = [0] * n
        for i in range(n):
            if col1[i] == 0:
                # 在树1 内，距离 i 为偶数的节点数就是 cnt1_0
                answer[i] = cnt1_0 + best2
            else:
                # col1[i] == 1 时，树1 内偶数距离节点数是 cnt1_1
                answer[i] = cnt1_1 + best2

        return answer