千问 LeetCode 3887. 增量偶权环查询 Python3实现

这道题的核心是带权并查集将环边权和为偶数转化为环上边权异或和为 0通过维护每个节点到根的异或距离来判断新边是否会形成奇权环。核心思路1. 问题转化边权为 0 或 1环的边权和为偶数 ⟺ 环上所有边权的异或和为 02. 维护目标如果图中所有环的异或和都为 0那么任意两点间任意路径的异或和都是唯一确定的与路径无关3. 带权并查集用 fa[x] 记录父节点dis[x] 记录 x 到父节点路径上的边权异或和。通过路径压缩find(x) 后 dis[x] 就是 x 到根的异或距离4. 判断逻辑对于边 (u, v, w)若 u、v 已在同一集合检查 dis[u] ^ dis[v] ^ w 是否为 0为 0 说明新环异或和为偶数可加入否则会产生奇权环跳过Python3 实现class Solution:def numberOfEdgesAdded(self, n: int, edges: list[list[int]]) - int:fa list(range(n))dis [0] * n # dis[x]: x 到 fa[x] 路径上的边权异或和def find(x: int) - int:带路径压缩的 find调用后 dis[x] 变为 x 到根的异或距离if fa[x] ! x:root find(fa[x])dis[x] ^ dis[fa[x]] # 累积异或距离fa[x] rootreturn fa[x]count 0for u, v, w in edges:ru, rv find(u), find(v)if ru rv:# 已在同一集合检查新环的异或和# 环的异或和 dis[u] ^ dis[v] ^ wif (dis[u] ^ dis[v] ^ w) 0:count 1 # 偶权环可以加入else:# 不在同一集合合并不会形成环# 需要让 dis[u] ^ dis[v] ^ w 0 成立# 即 dis[ru] dis[u] ^ dis[v] ^ wdis[ru] dis[u] ^ dis[v] ^ wfa[ru] rvcount 1return count关键点解析- 路径压缩时的异或更新dis[x] ^ dis[fa[x]] 是因为 x 到根的异或距离 x 到旧父节点的异或 ⊕ 旧父节点到根的异或- 合并时的权重设置合并 ru 和 rv 时设置 dis[ru] dis[u] ^ dis[v] ^ w保证合并后 u 和 v 之间的异或距离恰好等于 w- 时间复杂度O(m · α(n))其中 m 是边数α 是反阿克曼函数近似线性- 空间复杂度O(n)示例验证以 n3, edges[[0,1,1],[1,2,1],[0,2,1]] 为例1. 边 (0,1,1)0 和 1 不在同一集合合并count12. 边 (1,2,1)1 和 2 不在同一集合合并count23. 边 (0,2,1)0 和 2 已在同一集合环异或和 dis[0]^dis[2]^1 1^1^1 1奇数跳过最终返回 2与预期一致。需要我帮你整理一份带权并查集异或/加法的通用模板吗遇到类似题可以直接套用。