🎮 对称性的觉醒：当奇数和偶数平分天下

听说村长最近沉迷于一款叫《技能树大亨》的RPG游戏——我怀疑这老头把省下来的钱全充了Steam余额，账号时长怕不是比我刷题还多。今天一大早，我正蹲在锅炉边添柴，电脑屏幕突然弹出老头的远程协助请求。点下接受，村长的游戏画面直接投屏过来——他的人物正卡在技能树界面，鼠标在一棵枝繁叶茂的树状图上疯狂画圈，技能节点之间的连线旁还标注着"普通升级: 1点"和"强化升级: 2点"。

“小白！我的隐藏成就卡住了！“村长的声音从屏幕那头炸出来，急得像是副本门口等着拉人的团长，“从根技能1号出发，每条连线可以选普通升级花1点，或者强化升级花2点。隐藏成就叫’奇数流大师’，要求算出有多少种加点法能使到达最深那个终极技能的总消耗是奇数！”

我盯着屏幕，扫到成就描述末尾一行不起眼的小字——“忽略从根到最深节点路径外的所有边”。这不就把一棵树压缩成一条链吗？只有从根到最深节点的那条路径算数，其他枝丫全是气氛组，约等于RPG里站桩喊固定台词的NPC。问题瞬缩成两件事：第一，最深那层在哪儿——也就是最大深度k是多少；第二，这k条边上各赋1或2，总和为奇数的组合数是多少。

第一步：找深度是DFS的肌肉记忆

题目给的是无向树——边[1,2]表示1和2互通，虽然根定在1，但遍历必须双向通行，否则DFS 会困在叶子节点，剩下的分支全遍历不到。所以建邻接表时必须每条边两头都加——1的邻居里有2，2的邻居里也有1，双向车道全登记，DFS才能想去哪去哪。

但双向建图有一个经典坑——不记父节点的话，DFS会在父子之间来回横跳，像喝醉的勇者在两个房间之间来回读条，直到栈溢出教我做人。所以递归时带个fa参数当“防回退机制”——告诉DFS“你刚从你爸那儿过来，别再回去了”

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)
        
def dfs(x: int, fa: int) -> int:
    d = 0
    for y in g[x]:
        if y != fa:  # 不递归到父节点，防止无限循环
            d = max(d, dfs(y, x) + 1)
    return d

k = dfs(1, 0)

双向建图 + fa过滤 = 无向图当有向树遍历。叶子节点没有非父邻居，直接返回0；自底向上逐层加一，max取最大深度。这套组合拳打过无数次的DFS模板——就像RPG里的基础连招。

深度k到手。

第二步：奇偶性的对称美学

接下来是核心——k条边，每条1或2，总和为奇数的方案数。

1是奇数，2是偶数，总和为奇数等价于路径上有奇数个1。枚举C(k,1) + C(k,3) + C(k,5) + …？我数学早就连本带利还给老师了，组合数求和公式长啥样都忘了，更别说还要取模。

等等——换个思路：如果前k-1条边的和是偶数，最后一条只能选1把总和扳成奇数；前k-1条边的和是奇数，最后一条必须选2把总和保持奇数。

也就是说，前k-1条边可以自由发挥，最后一条边只能被迫营业——有且仅有一种选择能救场。所以总方案数就是前k-1条边的任意组合数——前k-1条每条自由选1或2，总共2^{k-1}种。

再往深层想的话，这可以说是奇偶对称性的必然结果：对于任意k≥1，在所有2^k种赋值中，权重和为奇数和偶数的方案数永远平分天下，各占一半。

这不是什么巧合，是奇偶性天生的对称：把最后一条边从1翻成2，奇偶就翻转，所有方案两两配对，恰好一半奇一半偶。所以答案=2^k / 2 = 2^{k-1}。不用枚举，不用求和，一行对称性直接秒杀。

return pow(2, k - 1, MOD)

pow(base, exp, mod)快速幂，底层用二分指数，O(log k)搞定，属实是标准库里的隐藏神器。

收工？

我敲下回车，屏幕那头村长的隐藏成就图标“叮”地一声亮了，金色光芒闪得他差点把电脑抱起来转圈。“拿到了！奇数流大师！我就知道找你是对的！” 村长的声音兴奋得像刚抽到SSR。

我刚想谦虚两句，突然看到游戏界面上弹出一个新的成就预告——“奇数流宗师：应对任意两个技能节点之间的路径，计算奇偶方案数，解锁终极加点方案”。

我心里咯噔一下。任意两个节点之间的路径？那可不是今天这种“从根到最深叶子”的单条快车道了——查询可能从任意节点出发，到任意节点结束，路径长度各不相同，有些说不定还会往上走到公共祖先再拐下去。奇偶对称性的核心没变，路径上有k条边，方案数还是2^{k-1}，但每条查询的k都不一样，怎么快速找出任意两点之间的距离？

我感觉自己的后背开始冒汗。

村长还在屏幕那头兴奋地嚷嚷：“小白，你看这个’奇数流宗师’成就，好像有点意思啊！要不你现在帮我看看……”

“今、今天就算了吧！“我慌忙打断他，“我得去……去添柴！锅炉要熄了！”

说完，我果断切断了远程连接，瘫在椅子上长长地舒了一口气。

明天的事，明天再说吧。

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。