无环无向图奇数边节点对计数：为何从奇度顶点搜索？

首先明确核心前提：无环无向图本质是森林，每个连通分量都是一棵树。我们要统计的路径长度为奇数的节点对，等价于树中深度奇偶性不同的节点对（这里的深度是相对于任意选定的根节点而言）。

为什么有人会从奇度顶点开始搜索？ #

这种思路大概率是混淆了树的欧拉路径特性：树作为连通无环图，其欧拉路径（遍历所有边恰好一次）必然起始和结束于奇度顶点（树中奇度顶点数量为偶数）。但回到统计奇数边节点对的问题，这个特性和统计目标没有直接关联——只是部分人可能将欧拉路径的起始规则迁移到了这里，但并非必要操作。

起始顶点的选择是否无关紧要？ #

结论是：完全无关紧要，不会影响最终统计结果。原因如下：

• 对于任意一棵树，假设以节点u为根时，奇深度节点数为a，偶深度节点数为b（a + b = n，n为树的节点数），那么该树贡献的奇数边节点对数量为a * b。
• 若更换根节点为v，设原根u到v的路径长度奇偶性为k（0代表偶数，1代表奇数）：
  • 若k=0（v原深度为偶数），所有节点的新深度奇偶性与原深度一致，a和b不变，a*b也不变；
  • 若k=1（v原深度为奇数），所有节点的新深度奇偶性反转，此时奇深度节点数变为b，偶深度变为a，但a*b = b*a，乘积仍然不变。
• 不管选择哪个节点作为根，每个连通分量的贡献值固定，总和自然也不会变化。

简言之，统计奇数边节点对的核心是计算每个树中奇偶深度节点数的乘积，起始顶点的选择只会改变“哪些节点被归为奇/偶深度”，但不会改变两者的乘积，因此对最终结果没有影响。

内容的提问来源于stack exchange，提问作者Aleksander Janic