思路讲解
下面把**“任意两点 u → v 经过哪些关键边”在 O(log n) 时间求出的方法补充得更细一些。**
给出两种写法：
A) 更快也更简单的一行式（查询 O(1)）
思路：
从根结点 root 出发 DFS，一路累积“根 → 当前结点”这条链上出现的关键边集合，记到数组 upMask[] 里。
1 | upMask[child] = upMask[parent] | (当前这条边是关键边 ? (1<<bit) : 0); |
因为一条树上路径 (u,v) 可以分解成
root → u 和 root → v 两条链，而它们公共的部分（root → lca）在两条链里都会出现一次，
用异或就能把它抵消掉，所以
1 | pathMask(u,v) = upMask[u] ^ upMask[v]; // O(1) |
整条路径上恰好出现一次的边，正好就是 u-v 之间的那条简单路径。
-
预处理：一次 DFS，O(n)。
-
查询：连 LCA 都不用求，完全 O(1)。
AC代码
源代码
1 |