🎮二进制传送门觉醒：当每个节点都能瞬间跳跃
今天一大早，我刚推开村口锅炉房的门，就看见村长蹲在那儿，顶着两个黑眼圈，怀里抱着笔记本电脑，屏幕上’‘奇数流宗师’‘几个烫金大字一闪一闪的，后面跟着密密麻麻的查询列表，滚动条缩成了一个小点。墨菲定律诚不欺我——怕什么来什么。
‘‘小白！‘‘村长看到我，像装了雷达一样从地上弹起来，‘‘这个成就太难了！你看，宗师成就要求处理任意两个节点之间的路径查询，不是只有根到叶子那么简单！‘‘他疯狂划拉屏幕，‘‘查询可能是从1号到5号，从3号到7号，从8号到2号……我把昨天你那套压扁成链的代码套进去，跑的我风扇狂转，Steam Deck差点起飞——结果还没跑完！’’
我心里一沉。昨天那是从根到最深叶子，路径只有一条，深度k固定，一行快速幂秒杀。今天是任意两点之间的路径——每条查询的起点终点都不一样，路径长度k各不相同。昨天的对称性trick倒是还能用——路径上有k条边，方案数还是2^{k-1}。但问题变成了：怎么快速算出任意两点间的路径长度？
我在草稿纸上开始画树。假设查询节点4和节点5，路径是4→3→5，长度是2，查询节点2和节点5，路径是2→1→3→5，长度是3。关键藏在这些路径的交汇处——它们不是一条直线冲到底的，而是先往上爬到某个公共祖先，再拐弯往下。那个’‘分叉点’‘就是最近公共祖先，LCA。那么，对于每个查询(u, v)，路径长度 k = depth[u] + depth[v] - 2*depth[LCA]。有了k，对称性trick照旧——方案数还是2^{k-1}。
关键在于，怎么快速找到LCA？
遇事不决先暴力？
既然LCA的定义是两个节点往上爬、第一个相遇的祖先，那最朴素的做法就是模拟这个爬树过程：从u一路爬到根，把沿途所有节点记下来；再从v一路爬到根，看哪个节点最先出现在u的路径里。
对于查询(u, v)，分别爬树记录路径，暴力比对找第一个共同节点： find_path(node) 函数记录从node到根节点的路径，find_lca_brute_force(u, v)函数暴力找u和v的最近公共祖先(LCA)。
# 暴力LCA解法：通过爬树找最近公共祖先
def assignEdgeWeights(edges: List[List[int]], queries: List[List[int]]) -> List[int]:
MOD = 1_000_000_007
n = len(edges) + 1
g = [[] for _ in range(n + 1)]
for x, y in edges:
g[x].append(y)
g[y].append(x)
# 预处理父节点和深度
parent = [0] * (n + 1) # parent[i]表示节点i的父节点
depth = [0] * (n + 1) # depth[i]表示节点i的深度
def dfs(x: int, fa: int) -> None:
parent[x] = fa
for y in g[x]:
if y != fa: # 避免回溯到父节点
depth[y] = depth[x] + 1
dfs(y, x)
dfs(1, 0) # 从根节点1开始DFS，根节点的父节点设为0（虚拟节点）
# 记录从node到根节点的路径列表（包含node和根节点）
def find_path_to_root(node: int) -> list:
path = []
current = node
while current != 0: # 一直爬到根节点的父节点（虚拟节点0）
path.append(current)
current = parent[current]
return path
# 暴力找u和v的最近公共祖先(LCA)
def find_lca_brute_force(u: int, v: int) -> int:
path_u = find_path_to_root(u)
path_v = find_path_to_root(v)
path_u_set = set(path_u) # 将path_u转为集合，方便快速查找
# 从v的路径往上找，第一个在u路径中的节点就是LCA
for node in path_v:
if node in path_u_set:
return node
return 1 # 理论上不会到这里，因为根节点一定是公共祖先
# 计算u到v的路径长度k = depth[u] + depth[v] - 2*depth[LCA]
def get_distance(u: int, v: int) -> int:
lca = find_lca_brute_force(u, v)
return depth[u] + depth[v] - 2 * depth[lca]
# 计算k条边的赋值方案中，使总和为奇数的方案数
def count_odd_ways(k: int) -> int:
return pow(2, k - 1, MOD) if k != 0 else 0
# 处理每个查询
answer = []
for x, y in queries:
if x == y: # 同一点，路径长度为0，方案数为0
answer.append(0)
else:
# 计算路径长度
path_length = get_distance(x, y)
# 计算方案数
answer.append(count_odd_ways(path_length))
return answer
我默默算了笔账：查询数量十万，每次暴力找LCA——find_path 爬树最坏O(n)，node in path_v 又是O(n)，总复杂度O(q*n)，十万乘十万，评测机不弹TLE才怪。
正一筹莫展，后脑勺挨了轻轻一下——力道依旧精准。老勇者的声音从背后传来：“又在暴力枚举？”
我捂着后脑勺，感觉救星到了。老勇者瞄了一眼屏幕上的查询列表，又看了一眼我的那段爬树代码，叹了口气：“你啊，总是用O(n)的方法硬刚O(log n)能解决的问题。告诉我，你知道倍增法求LCA吗？”
我心虚地缩了缩脖子：“听说过，Binary Lifting……但一直没学，总觉得二进制跳来跳去的有点玄乎……”
“二进制提升，求LCA的神器。“老勇者打了个响指，“准备让暴力爬树法退役吧，你该学点真正的树上跳跃姿势了！”
当LCA遇上二进制提升！
他在纸上画了一棵枝繁叶茂的大树，并在旁边写下几个大字——’’预处理 + 快速查询 = 降维打击’’。
“暴力法的痛点在哪？“老勇者指向树上的一个节点，“每次查询都要从节点一步步往上爬，像蜗牛一样。如果树退化成一条链，爬一次就是O(n)。十万次查询就是O(nq)，评测机不TLE才是见鬼了。”
‘‘不一步一步爬？‘‘我感到匪夷所思。毕竟在我的认知里，树只能沿着边往上走，要么dfs，要么bfs——就像RPG里爬塔，每层楼梯都得踩一遍，怎么可能跳过中间楼层直接到顶层？
‘’预处理。‘‘老勇者吐出三个字，‘‘提前给每个节点装上 ‘快捷传送门’——不只存它的父节点，而是存它的第1级祖先、第2级祖先、第4级祖先、第8级祖先……直到第2^16级祖先。这样查询的时候，你就可以’跳着走’，而不是’爬着走’。这就是二进制提升的名字由来——用2的幂次来加速跳跃。”
我挠头：‘‘为什么偏偏是2的幂次？’’
‘‘因为任何整数都可以拆成二进制。‘‘老勇者瞅了我一眼，‘‘比如13 = 8 + 4 + 1 = 2^3 + 2^2 + 2^0。如果你要往上跳13步，不用一步一步爬，只需要跳三次：先跳8步，再跳4步，最后跳1步。每次跳跃都是O(1)，总共O(log n)。从蜗牛进化成袋鼠，靠的就是二进制拆分。’’
他在纸上写下了核心定义：pa[x][i] = x的第2^i级祖先，也就是节点x向上跳2^i步到达的祖先。
‘‘哦——’’ 我若有所思，‘‘提前处理好节点的2的幂次级祖先们？可是这要怎么算？每个节点都跳一遍不还是炸？”
‘’动态规划。‘‘老勇者写下状态转移方程：pa[x][i+1] = pa[pa[x][i]][i]，’’ x的第2^{i+1}级祖先，等于x的第2^i级祖先再往上跳2^i步。’’
我感觉脑子有点转不过来：‘‘这不会跳错？套娃套得我头晕。’’
‘‘不会。‘‘老勇者画了个示意图，‘‘假设x的第2级祖先是a，a的第2级祖先是b。x到a是2步，a到b也是2步，那x到b就是4步——所以b就是x的第4级祖先。这个递推的精髓在于：用已知的短距离跳跃，组合出未知的长距离跳跃。2^i级的祖先你已经在上一轮算好了，拿它再跳一次2^i，就是2^{i+1}级。倍增就是这么来的——每一步都建立在之前所有步的基础上，像盖楼一样一层一层往上搭。’’
“DFS的时候，一边往下走一边顺手填。走到一个节点时，它的所有2的幂次祖先都已经在上层被算好了，你只需要用父节点的数据往上递推——pa[x][0]是父节点，pa[x][1]是爷爷，pa[x][2]是爷爷的爷爷，以此类推。一棵树遍历完，每个节点都自带一套二进制传送门，以后找LCA的时候，你就不需要再爬树了，直接让节点按二进制拆分往上层跳就行。’’
老勇者接着写下了完整的预处理代码：
class LcaBinaryLifting:
def __init__(self, edges: List[List[int]]):
n = len(edges) + 1
m = n.bit_length() # 计算需要多少层：log2(n)向上取整
g = [[] for _ in range(n)]
for x, y in edges:
x -= 1 # 节点编号从0开始（内部处理更方便）
y -= 1
g[x].append(y)
g[y].append(x)
# depth[i]: 节点i的深度（根节点深度为0）
depth = [0] * n
# pa[i][j]: 节点i的第2^j级祖先（-1表示不存在）
pa = [[-1] * m for _ in range(n)]
def dfs(x: int, fa: int) -> None:
pa[x][0] = fa # 第2^0=1级祖先就是父节点
for y in g[x]:
if y != fa:
depth[y] = depth[x] + 1
dfs(y, x)
dfs(0, -1) # 从根节点0开始DFS，根节点的父节点设为-1
# 动态规划计算更高级的祖先，状态转移 pa[x][i+1] = pa[pa[x][i]][i]
for i in range(m - 1):
for x in range(n):
if (p := pa[x][i]) != -1: # 如果2^i级祖先存在
pa[x][i + 1] = pa[p][i] # 计算2^(i+1)级祖先
self.depth = depth
self.pa = pa
“你看，“老勇者指着代码，“第一步，建图。第二步，DFS预处理每个节点的深度和直接父节点（pa[x] [0]）。第三步，动态规划计算更高级的祖先。外层循环 log n次，内层循环n次，总共n log n。”
他打了个比方：“预处理一次性完成，之后每次查询都能直接享受红利——就好比副本开荒前先把全图传送点踩一遍，开荒的时候直接飞过去，不用每次都从新手村跑图。”
我盯着代码看了一会，一拍大腿：“也就是说，预处理好了以后，找LCA就不需要一步一步爬树了，而是二进制跳跃！因为LCA肯定是两个节点都能跳到的地方——先让深度大的那个跳到和另一个同一高度，然后两个一起往上蹦，只要跳完之后两人不在同一个节点，就说明还没跳到公共祖先，继续往上跳！”
“是这个道理。” 老勇者竖起四根手指，“听好了，找LCA分四步——”
“第一步，对齐深度。确保x在y上方（depth[x] ≤ depth[y]），如果x更深就交换。然后把y往上跳，跳到和x同一深度。怎么跳？把深度差拆成二进制，按位跳——差13层就先跳8层再跳4层再跳1层。”
“第二步，来个判断——如果跳完之后y == x，说明x本身就是y的祖先，直接返回x。这种情况比如x是y的爷爷，把y提到x的高度之后，发现两人站在同一个节点上，那LCA就是x。”
“第三步，同时倍增跳跃。让x和y从大到小尝试往上跳——从最大的步长（比如2^16）开始试。如果跳完之后x和y的祖先还不一样，说明LCA还在上面，那就跳；如果一样了，说明已经跳到LCA或LCA以上了，就不跳。循环走完，x和y会停在LCA的紧下方——也就是LCA的下一层。”
“第四步，返回它们的父节点pa[x][0]，就是LCA。”
class LcaBinaryLifting:
def __init__(self, edges: List[List[int]]):
......
self.depth = depth
self.pa = pa
def get_kth_ancestor(self, node: int, k: int) -> int:
for i in range(k.bit_length()): # 遍历k的每一位二进制位
if k >> i & 1: # k 二进制从低到高第 i 位是 1；
node = self.pa[node][i] # 往上跳2^i步
return node
def get_lca(self, x: int, y: int) -> int:
if self.depth[x] > self.depth[y]:
x, y = y, x # 确保x的深度不大于y
# 1. 使y和x在同一深度
y = self.get_kth_ancestor(y, self.depth[y] - self.depth[x])
# 2. 检查是否重合
if y == x:
return x # x本身就是y的祖先
# 3. 倍增跳跃：从最大的步长开始尝试
for i in range(len(self.pa[x]) - 1, -1, -1):
px, py = self.pa[x][i], self.pa[y][i]
if px != py:
x, y = px, py # 同时往上跳 2**i 步
# 4. 此时x和y的父节点就是LCA
return self.pa[x][0]
我盯着那段for i in range(len(self.pa[x]) - 1, -1, -1)的代码，有点困惑：“为什么要从大到小跳？”
“因为要尽快接近LCA，但又不能跳过。“老勇者打了个比方，“就像用砝码称重——先试最大的砝码，太重的就撤掉，刚好就留着，这样精度最高。从小到大跳的话，你跳完1步、2步、4步……到后面可能会跳过LCA，还得退回来，退回来又不知道退多少。从大到小是贪心，每次跳最大可能的步数，但保证不跳过LCA——因为跳过的话 pa[x][i] == pa[y][i]，说明这步太大了，LCA在下面，就不跳。这样就能保证每次都能最大程度地接近LCA，最终刚好卡在LCA正下方，再往上一步就是LCA。”
我反应过来了：“所以最后返回pa[x][0]——x的父节点——就是LCA？预处理O(n log n)，查询O(log n)，这就是二进制提升找LCA的威力？”
“没错。“老勇者点点头，话锋一转，“来，LCA有了，路径长度怎么算？你之前推导过。”
我愣了一下，脑子里迅速回放开始写的公式：“k = depth[u] + depth[v] - 2*depth[LCA]！“抄起键盘补上：
class LcaBinaryLifting:
......
def get_dis(self, x: int, y: int) -> int:
return self.depth[x] + self.depth[y] - self.depth[self.get_lca(x, y)] * 2
老勇者满意地点点头：“LCA拿到，套公式算出k，再套昨天的对称性结论——方案数 = 2^{k-1}，这题就解决了。”
他顺手补上主函数，一行列表推导式，对每个查询(x, y)，如果x == y，答案是0；否则答案是2^{路径长度减一}：
# 预处理2的幂（用于快速计算方案数）
MOD = 1_000_000_007
POW2 = [0] * 10 ** 5
POW2[0] = 1
for i in range(1, len(POW2)):
POW2[i] = POW2[i - 1] * 2 % MOD
class Solution:
def assignEdgeWeights(self, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
g = LcaBinaryLifting(edges) # 初始化LCA结构
return [
POW2[g.get_dis(x - 1, y - 1) - 1] if x != y else 0
for x, y in queries
]
我盯着那段 POW2 数组：“为什么不直接用 pow(2, k-1, MOD)？Python内置的快速幂不是挺快吗？”
老勇者瞪了我一眼，恨铁不成钢地说：“还是预处理！pow 再快也是快速幂，十万次查询，每次O(log k)，就是十万乘十七，一百七十万次运算。但如果提前把2的幂打好表——POW2[i] = 2^i mod MOD——预处理O(n)一次性搞定，之后每次查表O(1)。空间换时间，经典到不能再经典的套路。”
我这才醒悟过来，“哦——就像游戏里提前算好所有技能伤害表，战斗时直接查，不用现场按计算器！”
“总算回过神了你。“老勇者点点头，“不过记住，预处理的数组大小要掐准数据范围。题目n ≤ 10^5，POW2开10^5就够。开小了查询越界，开大了浪费内存——这就是程序员的’度’。”
终章
我把整套代码拼起来，提交。屏幕上的查询列表飞速滚动，一个一个2^{k-1}弹出来，快得像是开了倍速——村长的Steam Deck传来一声清脆的 ‘叮’——‘‘奇数流宗师’‘成就图标从灰色变成金色，再从金色变成带粒子特效的彩虹色，老头激动得差点把电脑举过头顶，“拿到了！宗师！双层成就！我就知道找你是对的！”
我靠在椅背上，盯着那串 LcaBinaryLifting 的代码，想要把它刻进脑袋里——毕竟学会了树上跳跃的神功，我可不想再一步一步蜗牛爬了。老勇者这招“二进制提升”，听起来像黑客，用起来像开挂，真香。
村长抱着电脑乐颠颠地回去了，Steam Deck的风扇声从远处传来，不知道他又在肝什么新成就。我合上魔法书，往锅炉里添了根柴。今天的树上轻功够我消化几天了——下次再见到老勇者，我一定要把倍增表倒背如流。
本作品采用
知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议
进行许可。