科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文以 codeforces-go 仓库中 LeetCode 双周赛 176 第 4 题题解 为骨架完整还原树上的回文路径查询Palindromic Path Queries in a Tree从等价转化、静态查询到动态更新的完整推导过程。读完本文你将掌握一套可复用的路径奇偶性 → 二进制掩码 → LCA 抵消 → DFS 时间戳区间化 → 差分树状数组五步套路并看到它在 Python / Java / C / Go 四种语言中的落地实现与仓库内的源码佐证。题目背景与仓库位置这是 LeetCode 双周赛第 176 场的最后一题题目为Palindromic Path Queries in a Tree。给定一棵 $n$ 个节点的树节点编号 $0 \sim n-1$根为 $0$每个节点上有一个小写字母需要支持两类操作update x c把节点 $x$ 的字母改成 $c$query x y判断从 $x$ 到 $y$ 的唯一简单路径上的字母能否重排成一个回文串。在仓库中该题的完整资料位于leetcode/biweekly/176/d/目录README.md完整题解前置知识、推导、四语言代码、复杂度分析d.goGo 参考实现与 README 中的sol-Go代码一致d_test.go测试入口d.txt样例数据。可以看到仓库的每道题都遵循题解文档 可运行实现 测试用例三位一体的组织方式这为复盘与复用模板提供了极大便利。前置知识解题的四块拼图本题本质上是多个经典模板的组合拳题解开头给出了四条前置依赖2791. 树中可以形成回文的路径数静态版只查询不修改——它给出了本题最关键的等价转化最近公共祖先LCA——用于拼接任意两点间的路径3515. 带权树中的最短路径——给出了DFS 时间戳 差分树状数组处理子树区间更新的范式231. 2 的幂——提供了二进制数中至多一个 1的位运算判定法。下面逐一展开这四块拼图是如何被组装起来的。拼图一回文判定等价于至多一个奇数次字母根据 2791 题的结论一条路径上的字母若能重排成回文串当且仅当路径上至多有一个字母的出现次数是奇数其余字母必须两两成对。因此query x y等价于判断从 $x$ 到 $y$ 的路径上至多有一个字母的出现次数是奇数。由于字母只有 26 个可以用一个 26 位的二进制数表示路径上每个字母出现次数的奇偶性第 $k$ 位为 1 表示字母 $k$即ak出现了奇数次。于是至多一个字母出现奇数次就变成判断这个二进制数要么是 $0$全偶数可重排成镜像回文要么形如 $2^k\ (k\ge 0)$恰有一个 1即恰一个字母出现奇数次可放在回文串正中间。这两个条件合起来正是2 的幂的判定式res 0 || res (res - 1) 0而在本题的位运算实现中更简洁地写成res (res - 1) 0因为 $0 (-1) 0$ 同样成立。拼图二LCA 倍增模板树上任意两点 $x,y$ 之间的路径可以分解为$x$ 到 LCA $y$ 到 LCA两段。仓库的 graph_tree.go 在 L1137-L1138 注释最近公共祖先 · 其一 · 基于树上倍增下给出了完整的倍增 LCA 模板见 L1194 的lcaBinaryLifting本题直接用到了其中的getLCA与跳深度两个核心操作。处理 query异或前缀 LCA 抵消有了奇偶性掩码剩下的问题是如何高效求出任意两点路径的奇偶性掩码。定义$\textit{XOR}[i]$ 表示从根 $0$ 到节点 $i$ 的路径上字母出现次数的奇偶性对应的二进制数。它可以在一次自顶向下的 DFS 中递推求出XOR[0] 1 (s[0] - a) XOR[y] XOR[x] ^ (1 (s[y] - a)) // 边 x-yx 是 y 的父节点关键性质根据异或运算相同抵消的性质从 $x$ 到 $y$ 的路径的奇偶性掩码等于以下三者的异或和$0$ 到 $x$ 的路径奇偶性 $\textit{XOR}[x]$$0$ 到 $y$ 的路径奇偶性 $\textit{XOR}[y]$由于上面两条路径在 $x$ 与 $y$ 的最近公共祖先 $\textit{lca}$ 处重叠了一段被抵消了需要把 $\textit{lca}$ 本身的字母加回来即异或1 (s[lca] - a)。即query(x, y) 的掩码 XOR[x] ^ XOR[y] ^ (1 (s[lca] - a))直觉上可以这样理解$\textit{XOR}[x] \oplus \textit{XOR}[y]$ 得到的是$0$→$x$与$0$→$y$两条路径的对称差它正好是 $x \to y$ 的路径、但缺了 LCA 处那个字母因为它在两条前缀路径中各出现一次被抵消了补上它即可。这一手异或抵消 补回 LCA正是 2791 题解的核心思想。处理 updateDFS 时间戳 子树区间化 差分树状数组静态查询容易难的是修改。关键问题是当我们修改 $s[x]$ 后哪些 $\textit{XOR}[i]$ 会变变成什么了观察$\textit{XOR}[i]$ 对应从 $0$ 到 $i$ 的路径如果这条路径经过节点 $x$那么 $\textit{XOR}[i]$ 就会受影响。而路径经过 $x$恰好等价于$i$ 在子树 $x$ 中。所以修改 $s[x]$ 后只有子树 $x$ 内的节点 $i$ 的 $\textit{XOR}[i]$ 会变。变化量把原来的 $s[x]$ 擦除、换成新字母 $c$所有受影响节点的 $\textit{XOR}[i]$ 都要异或上同一个值val (1 (s[x] - a)) ^ (1 (c - a))旧字母的奇偶位被翻回、新字母的奇偶位被翻出其余位不动。子树如何变成区间这正是 3515 题引入的利器——DFS 时间戳。在做 DFS 时给每个节点记录进入时间戳 $\textit{tin}[x]$ 和退出时间戳 $\textit{tout}[x]$子树内最后一个被访问节点的时间戳。由于 DFS 的性质子树 $x$ 中所有节点的进出时间戳都落在闭区间 $[\textit{tin}[x], \textit{tout}[x]]$ 内。于是子树 $x$ 中所有 $\textit{XOR}[i]$ 异或 $val$就变成了区间 $[\textit{tin}[x], \textit{tout}[x]]$ 上的所有下标异或 $val$即标准的区间更新操作。区间异或更新 单点查询用什么最适合的数据结构是差分树状数组把区间更新转换成单点更新 前缀查询。做法同 3515 题——对区间 $[l, r]$ 整体异或 $val$等价于在差分序列上做两次单点异或update(tin[x], val) update(tout[x] 1, val) // 区间外恢复查询时节点 $i$ 的 $\textit{XOR}[i]$ 当前值 初始值 $\oplus$ 差分树状数组的前缀查询结果pre(tin[i])。实现细节这里树状数组存的是区间更新操作的异或结果不保存初始值$\textit{XOR}[i]$两者在查询时才合并。这与 2791 题纯静态、无需树状数组和 3515 题带权树最短路径同样用差分树状数组做区间异或形成了递进关系。仓库源码佐证Go 实现与 README 完全对应仓库的 d.go 与 README 中的sol-Go完全一致两者互为印证。关键部分L11-L34基于异或的fenwick树状数组update做单点异或、pre做前缀异或L44-L66倍增表pa、深度dep、时间戳timeIn/timeOut、根路径奇偶掩码pathXorFromRoot的 DFS 初始化L80-L103uptoDep跳深度与getLCA倍增 LCAL107-L127本题核心逻辑——update分支对[timeIn[x], timeOut[x]]做两次差分异或更新query分支用pathXorFromRoot[x] ^ pathXorFromRoot[y] ^ f.pre(timeIn[x]) ^ f.pre(timeIn[y]) ^ (1 (t[lca]-a))拼出路径掩码最后用res (res-1) 0判定回文可行性。注意query分支中多了f.pre(timeIn[x]) ^ f.pre(timeIn[y])两项——它们把历史 update 对 $\textit{XOR}[x]$ 与 $\textit{XOR}[y]$ 造成的增量补了回来这正是初始值 $\oplus$ 差分前缀结果的体现。测试用例与样例数据d_test.go 通过testutil.RunLeetCodeFuncWithFile从 d.txt 读取样例并逐组校验。d.txt 中给出了两组数据3 [[0,1],[1,2]] aac [query 0 2,update 1 b,query 0 2] [true,false]第一组树是一条链0-1-2字母依次为a a c。路径0→2的字母为a a c可重排成aca返回true把节点 1 改为b后路径变为a b c三个字母均只出现一次无法成回文返回false。4 [[0,1],[0,2],[0,3]] abca [query 1 2,update 0 b,query 2 3,update 3 a,query 1 3] [false,false,true]第二组星形树0 为根连 1、2、3。query 1 2的路径为b a两字母各一次→false把根改为b后query 2 3为a a→ 仍false两字母各一次…按输出应为false再把节点 3 改为a后query 1 3为b a a→ 可重排为aba返回true。树状数组与 LCA 的通用模板本题的两个模板在仓库copypasta目录中均有沉淀fenwick_tree.go 从 L106 起定义了通用fenwick类型注释中系统整理了树状数组的题单与经典扩展值域树状数组、树状数组套权值树等graph_tree.go 在 L1194 提供了lcaBinaryLifting树上倍增模板。也就是说本文推导出的五步套路在仓库里是开箱即用的组合模板lcaBinaryLiftingLCA 深度 时间戳 异或版fenwick差分区间更新 位运算奇偶掩码。完整实现四语言题解为四种语言各提供了完整实现。其公共部分是同一套算法骨架仅模板风格不同。GoGo 版与仓库 d.go 完全一致要点如下// 异或版树状数组a[i] ^ val前缀异或和 pre(i) type fenwick []int func newFenwickTree(n int) fenwick { return make(fenwick, n1) // 使用下标 1 到 n } func (f fenwick) update(i int, val int) { for ; i len(f); i i -i { f[i] ^ val } } func (f fenwick) pre(i int) (res int) { for ; i 0; i i - 1 { res ^ f[i] } return } func palindromePath(n int, edges [][]int, s string, queries []string) (ans []bool) { g : make([][]int, n) for _, e : range edges { x, y : e[0], e[1] g[x] append(g[x], y) g[y] append(g[y], x) } mx : bits.Len(uint(n)) pa : make([][16]int, n) dep : make([]int, n) timeIn : make([]int, n) // DFS 时间戳 timeOut : make([]int, n) clock : 0 pathXorFromRoot : make([]int, n) // 从根开始的路径中的字母奇偶性的集合 pathXorFromRoot[0] 1 (s[0] - a) var dfs func(int, int) dfs func(x, p int) { pa[x][0] p clock timeIn[x] clock for _, y : range g[x] { if y ! p { dep[y] dep[x] 1 pathXorFromRoot[y] pathXorFromRoot[x] ^ 1(s[y]-a) dfs(y, x) } } timeOut[x] clock } dfs(0, -1) // 倍增表 for i : range mx - 1 { for x : range pa { if p : pa[x][i]; p ! -1 { pa[x][i1] pa[p][i] } else { pa[x][i1] -1 } } } // 跳到指定深度 uptoDep : func(x, d int) int { for k : uint32(dep[x] - d); k 0; k k - 1 { x pa[x][bits.TrailingZeros32(k)] } return x } // 最近公共祖先 getLCA : func(x, y int) int { if dep[x] dep[y] { x, y y, x } y uptoDep(y, dep[x]) // 使 y 和 x 在同一深度 if y x { return x } for i : mx - 1; i 0; i-- { if px, py : pa[x][i], pa[y][i]; px ! py { x, y px, py // 同时往上跳 2^i 步 } } return pa[x][0] } // 上面全是模板下面开始本题逻辑 t : []byte(s) f : newFenwickTree(n) // 注意树状数组是异或运算 for _, q : range queries { if q[0] u { x, _ : strconv.Atoi(q[7 : len(q)-2]) c : q[len(q)-1] val : 1(t[x]-a) ^ 1(c-a) // 擦除旧的换上新的 t[x] c // 子树 x 全部异或 val转换成对区间 [timeIn[x], timeOut[x]] 的差分更新 f.update(timeIn[x], val) f.update(timeOut[x]1, val) } else { q q[6:] i : strings.IndexByte(q, ) x, _ : strconv.Atoi(q[:i]) y, _ : strconv.Atoi(q[i1:]) lca : getLCA(x, y) res : pathXorFromRoot[x] ^ pathXorFromRoot[y] ^ f.pre(timeIn[x]) ^ f.pre(timeIn[y]) ^ 1(t[lca]-a) ans append(ans, res(res-1) 0) // 至多一个字母的出现次数是奇数 } } return }PythonPython 版把模板拆成两个类FenwickTree异或版本与LcaBinaryLifting在 DFS 中同时求出深度、倍增表、时间戳与根路径奇偶掩码主逻辑在Solution.palindromePathclass FenwickTree: def __init__(self, n: int): self.tree [0] * (n 1) # 使用下标 1 到 n # a[i] ^ val1 i nO(log n) def update(self, i: int, val: int) - None: t self.tree while i len(t): t[i] ^ val i i -i # 前缀异或和 a[1] ^ ... ^ a[i]1 i nO(log n) def pre(self, i: int) - int: t self.tree res 0 while i 0: res ^ t[i] i i - 1 return res class LcaBinaryLifting: def __init__(self, edges, s): n len(edges) 1 m n.bit_length() g [[] for _ in range(n)] for x, y in edges: g[x].append(y) g[y].append(x) depth [0] * n pa [[-1] * n for _ in range(m)] tin [0] * n # DFS 时间戳 tout [0] * n clock 0 path_xor_from_root [0] * n # 从根开始的路径的字母出现次数的奇偶性 path_xor_from_root[0] 1 s[0] def dfs(x, fa): nonlocal clock pa[0][x] fa clock 1 tin[x] clock for y in g[x]: if y ! fa: depth[y] depth[x] 1 path_xor_from_root[y] path_xor_from_root[x] ^ (1 s[y]) dfs(y, x) tout[x] clock dfs(0, -1) for i in range(m - 1): for x in range(n): if (p : pa[i][x]) ! -1: pa[i 1][x] pa[i][p] self.depth, self.pa, self.tin, self.tout depth, pa, tin, tout self.path_xor_from_root path_xor_from_root def get_kth_ancestor(self, node, k): pa self.pa for i in range(k.bit_length()): if k i 1: node pa[i][node] if node 0: return -1 return node def get_lca(self, x, y): if self.depth[x] self.depth[y]: x, y y, x y self.get_kth_ancestor(y, self.depth[y] - self.depth[x]) # 使 y 和 x 在同一深度 if y x: return x pa self.pa for i in range(len(pa) - 1, -1, -1): px, py pa[i][x], pa[i][y] if px ! py: x, y px, py # 同时往上跳 2**i 步 return pa[0][x]update与query的处理逻辑与 Go 版逐行对应update 用val (1 t[x]) ^ (1 c)擦旧换新并在tin[x]与tout[x]1两处做差分更新query 用path_xor_from_root[x] ^ path_xor_from_root[y] ^ f.pre(tin[x]) ^ f.pre(tin[y]) ^ (1 t[lca])求路径掩码再以res (res-1) 0判定。Java 与 C两者结构与 Python 完全一致仅模板风格差异JavaFenwickTree用int[] treeupdate循环为for (; i tree.length; i i -i)LcaBinaryLifting的倍增层数为m 32 - Integer.numberOfLeadingZeros(n)getKthAncestor用Integer.numberOfTrailingZeros(k)取最低位的 1CFenwickTree是templatetypename T泛型题解注释提示按题意可用FenwickTreeint或FenwickTreelong long倍增层数为bit_width((uint32_t)n)get_kth_ancestor用countr_zero((uint32_t)k)。两种语言中 LCA 的跳深度写法略有差异但语义相同把k的二进制最低位逐个清掉每清一位就沿对应倍增表跳一次。复杂度分析设 $q$ 为queries的长度$n$ 为节点数时间复杂度$\mathcal{O}((nq)\log n)$。预处理 DFS 建倍增表为 $\mathcal{O}(n\log n)$每个 update 做两次树状数组更新、每个 query 做两次前缀查询加一次 LCA均为 $\mathcal{O}(\log n)$。题解特别指出把字符串形式的数字转成整数的开销也是 $\mathcal{O}(\log n)$因为数字长度不超过 $n-1$ 的十进制长度因此整体复杂度不变空间复杂度$\mathcal{O}(n\log n)$倍增表返回值不计入。相比朴素做法每次 query 暴力遍历路径、每次 update 重算子树内所有前缀掩码的 $\mathcal{O}(qn)$ 或 $\mathcal{O}(n^2)$该方案是压倒性的优化也说明时间戳区间化 差分 BIT是树动态查询类题目的标准姿势。专题训练与延伸题解在末尾给出了两条复习路线对应作者的树题单与数据结构题单树题单的「§3.7 DFS 时间戳」与「§3.8 最近公共祖先LCA」——本次的两个核心树工具数据结构题单的「§1.4 状态压缩前缀和」与「§8.1 树状数组」——奇偶掩码与差分 BIT 的来源。此外本题的完整知识链可映射到更宽的分类题单位运算奇偶掩码与res (res-1)判单一位、图论算法树上倍增 LCA、常用数据结构树状数组的区间更新单点查询、链表树与回溯DFS 时间戳等。想巩固树结构题也可以对照仓库 graph_tree.go 中更多的 LCA 应用如路径长度、路径上点分类讨论等 L1250-L1323自行刷题验证。小结回看整道题它展示了竞赛中非常典型的问题转化 模板组合思维链回文 → 奇偶性重排回文等价于至多一个奇数次字母2791 题的结论奇偶性 → 二进制26 位掩码异或天然描述出现次数奇偶性的变化路径 → 前缀异或$\textit{XOR}[x] \oplus \textit{XOR}[y]$ 拼接任意两点路径再用 LCA 补回重叠段修改 → 子树 → 区间DFS 时间戳把子树映射为连续区间 $[\textit{tin}, \textit{tout}]$区间异或 → 差分树状数组区间更新转为两次单点更新单点查询转为前缀异或。这五步环环相扣每一步都建立在前置题目之上。在 codeforces-go 仓库中这些模板异或 fenwick、倍增 LCA既是本题的实现也是可复用的通用件——下次遇到树上路径奇偶性 动态修改的题目直接按这条流水线套模板即可。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go中的树链剖分路径查询与更新codeforces go中的树链剖分路径查询与更新 树链剖分Heavy Light Decomposition, HLD是解决树上路径查询与更新问题的高科学计算如何快速微调MobileViTv2模型以适应特定领域任务完整指南如何快速微调MobileViTv2模型以适应特定领域任务完整指南 想要将预训练的MobileViTv2模型应用于医疗影像、卫星图像或工业质检等特定领域吗这篇探索Z-Image-Turbo-bf16的文本编码器Qwen3-4B如何精准理解复杂绘画指令探索Z Image Turbo bf16的文本编码器Qwen3 4B如何精准理解复杂绘画指令 在当今AI图像生成领域Z Image Turbo bf16凭借上一篇如何在Linux系统上快速安装JDK8完整的开发环境搭建教程下一篇mbedtls与OpenSSL性能对比嵌入式环境下的加密库选型指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考