LeetCode 3373. 连接两棵树后最大目标节点数目 II — Python3 实现
题目描述
有两棵无向树，分别有 `n` 和 `m` 个节点。给定两棵树的边 `edges1` 和 `edges2`。
如果节点 `u` 和节点 `v` 之间路径的边数是偶数，则称 `u` 是 `v` 的目标节点。一个节点一定是它自己的目标节点。
返回长度为 `n` 的数组 `answer`，`answer[i]` 表示将第一棵树中节点 `i` 与第二棵树中某个节点连接一条边后，第一棵树中节点 `i` 的目标节点数目的最大值。
核心思路：黑白染色法（BFS）
树是二分图，可以用 0/1 染色来区分节点深度的奇偶性：
- 相邻节点颜色不同（0 和 1 交替）
- 相同颜色的节点之间距离为偶数（目标节点关系）
- 不同颜色的节点之间距离为奇数
所以对每棵树染色后，统计颜色 0 和颜色 1 的节点数量即可。
对于第一棵树的节点 `i`：
- 树1中的目标节点 = 与 `i` 同色的节点数
- 连接树2后，树2中的目标节点 = 可以选择树2中颜色更多的那一类（通过选择连接树2中对应颜色的节点，使距离为偶数）
Python3 实现
```python
from typing import List
from collections import deque
class Solution:
def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:
n = len(edges1) + 1
m = len(edges2) + 1
# 构建邻接表
def build_graph(edges):
size = len(edges) + 1
g = [[] for _ in range(size)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
return g
g1 = build_graph(edges1)
g2 = build_graph(edges2)
# BFS 染色，返回 (颜色数组, [颜色0数量, 颜色1数量])
def bfs_color(graph):
size = len(graph)
color = [-1] * size
q = deque([0])
color[0] = 0 # 根节点染成颜色0
while q:
u = q.popleft()
for v in graph[u]:
if color[v] == -1:
color[v] = color[u] ^ 1 # 相邻节点颜色翻转
q.append(v)
count = [0, 0]
for c in color:
count[c] += 1
return color, count
# 对两棵树分别染色
color1, count1 = bfs_color(g1)
_, count2 = bfs_color(g2)
# 树2中能贡献的最大目标节点数（选颜色多的那一类）
max_from_tree2 = max(count2)
# 计算答案
ans = []
for i in range(n):
# 树1中同色节点数 + 树2中最大可贡献节点数
ans.append(count1[color1[i]] + max_from_tree2)
return ans
```
更简洁的写法
```python
from typing import List
from collections import deque
class Solution:
def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) -> List[int]:
def solve(edges):
n = len(edges) + 1
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
color = [-1] * n
q = deque([0])
color[0] = 0
cnt = [0, 0]
cnt[0] = 1
while q:
u = q.popleft()
for v in g[u]:
if color[v] == -1:
color[v] = color[u] ^ 1
cnt[color[v]] += 1
q.append(v)
# 返回每个节点i的同色节点数（即目标节点数）
return [cnt[color[i]] for i in range(n)]
cnt1 = solve(edges1)
cnt2 = solve(edges2)
max2 = max(cnt2)
return [x + max2 for x in cnt1]
```
复杂度分析
指标 复杂度
时间 O(n + m) — 每棵树 BFS 遍历一次
空间 O(n + m) — 邻接表 + 颜色数组
关键点说明
1. 染色原理：树是二分图，相邻节点颜色不同。相同颜色节点之间的距离为偶数（目标节点），不同颜色为奇数。
2. 树2的贡献：对于树2，我们可以自由选择连接哪个节点：
- 如果树2中颜色0的节点更多，就将树1的节点连接到树2中颜色1的节点上，这样树2中所有颜色0的节点到树1节点的距离都是偶数（1+奇数=偶数）
- 反之亦然
- 所以树2的贡献恒为 `max(count2[0], count2[1])`
3. 树1的贡献：节点 `i` 的目标节点就是树1中与它同色的所有节点，即 `count1[color1[i]]`
4. 最终答案：`answer[i] = count1[color1[i]] + max(count2[0], count2[1])`
验证示例
示例 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]]`
- 树1染色：节点 0(0), 1(1), 2(1), 3(0), 4(0) → 颜色0: 3个, 颜色1: 2个
- 树2染色：颜色0: 3个, 颜色1: 5个 → max = 5
- `answer[0] = 3 + 5 = 8`, `answer[1] = 2 + 5 = 7` → [8,7,7,8,8] ✓
示例 2：`edges1 = [[0,1],[0,2],[0,3],[0,4]], edges2 = [[0,1],[1,2],[2,3]]`
- 树1染色：节点 0(0), 1(1), 2(1), 3(1), 4(1) → 颜色0: 1个, 颜色1: 4个
- 树2染色：颜色0: 2个, 颜色1: 2个 → max = 2
- `answer[0] = 1 + 2 = 3`, `answer[1] = 4 + 2 = 6` → [3,6,6,6,6] ✓
