LeetCode 3373. 连接两棵树后最大目标节点数目 II — Python3 实现题目描述有两棵无向树分别有 n 和 m 个节点。给定两棵树的边 edges1 和 edges2。如果节点 u 和节点 v 之间路径的边数是偶数则称 u 是 v 的目标节点。一个节点一定是它自己的目标节点。返回长度为 n 的数组 answeranswer[i] 表示将第一棵树中节点 i 与第二棵树中某个节点连接一条边后第一棵树中节点 i 的目标节点数目的最大值。核心思路黑白染色法BFS树是二分图可以用 0/1 染色来区分节点深度的奇偶性- 相邻节点颜色不同0 和 1 交替- 相同颜色的节点之间距离为偶数目标节点关系- 不同颜色的节点之间距离为奇数所以对每棵树染色后统计颜色 0 和颜色 1 的节点数量即可。对于第一棵树的节点 i- 树1中的目标节点 与 i 同色的节点数- 连接树2后树2中的目标节点 可以选择树2中颜色更多的那一类通过选择连接树2中对应颜色的节点使距离为偶数Python3 实现pythonfrom typing import Listfrom collections import dequeclass Solution:def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) - List[int]:n len(edges1) 1m len(edges2) 1# 构建邻接表def build_graph(edges):size len(edges) 1g [[] for _ in range(size)]for u, v in edges:g[u].append(v)g[v].append(u)return gg1 build_graph(edges1)g2 build_graph(edges2)# BFS 染色返回 (颜色数组, [颜色0数量, 颜色1数量])def bfs_color(graph):size len(graph)color [-1] * sizeq deque([0])color[0] 0 # 根节点染成颜色0while 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] 1return 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更简洁的写法pythonfrom typing import Listfrom collections import dequeclass Solution:def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) - List[int]:def solve(edges):n len(edges) 1g [[] for _ in range(n)]for u, v in edges:g[u].append(v)g[v].append(u)color [-1] * nq deque([0])color[0] 0cnt [0, 0]cnt[0] 1while q:u q.popleft()for v in g[u]:if color[v] -1:color[v] color[u] ^ 1cnt[color[v]] 1q.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])验证示例示例 1edges1 [[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] ✓示例 2edges1 [[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] ✓
Kimi LeetCode 3373. 连接两棵树后最大目标节点数目 II Python3实现
LeetCode 3373. 连接两棵树后最大目标节点数目 II — Python3 实现题目描述有两棵无向树分别有 n 和 m 个节点。给定两棵树的边 edges1 和 edges2。如果节点 u 和节点 v 之间路径的边数是偶数则称 u 是 v 的目标节点。一个节点一定是它自己的目标节点。返回长度为 n 的数组 answeranswer[i] 表示将第一棵树中节点 i 与第二棵树中某个节点连接一条边后第一棵树中节点 i 的目标节点数目的最大值。核心思路黑白染色法BFS树是二分图可以用 0/1 染色来区分节点深度的奇偶性- 相邻节点颜色不同0 和 1 交替- 相同颜色的节点之间距离为偶数目标节点关系- 不同颜色的节点之间距离为奇数所以对每棵树染色后统计颜色 0 和颜色 1 的节点数量即可。对于第一棵树的节点 i- 树1中的目标节点 与 i 同色的节点数- 连接树2后树2中的目标节点 可以选择树2中颜色更多的那一类通过选择连接树2中对应颜色的节点使距离为偶数Python3 实现pythonfrom typing import Listfrom collections import dequeclass Solution:def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) - List[int]:n len(edges1) 1m len(edges2) 1# 构建邻接表def build_graph(edges):size len(edges) 1g [[] for _ in range(size)]for u, v in edges:g[u].append(v)g[v].append(u)return gg1 build_graph(edges1)g2 build_graph(edges2)# BFS 染色返回 (颜色数组, [颜色0数量, 颜色1数量])def bfs_color(graph):size len(graph)color [-1] * sizeq deque([0])color[0] 0 # 根节点染成颜色0while 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] 1return 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更简洁的写法pythonfrom typing import Listfrom collections import dequeclass Solution:def maxTargetNodes(self, edges1: List[List[int]], edges2: List[List[int]]) - List[int]:def solve(edges):n len(edges) 1g [[] for _ in range(n)]for u, v in edges:g[u].append(v)g[v].append(u)color [-1] * nq deque([0])color[0] 0cnt [0, 0]cnt[0] 1while q:u q.popleft()for v in g[u]:if color[v] -1:color[v] color[u] ^ 1cnt[color[v]] 1q.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])验证示例示例 1edges1 [[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] ✓示例 2edges1 [[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] ✓
