我建立了一个质心分解树，并且我有一个返回质心和其他顶点之间距离的函数。
我有一个问题，如何根据这些数据计算：它们之间的距离为奇数的顶点对的数量？
使用两个变量来跟踪与前一个子树中的质心距离为偶数（从 1 开始，因为质心距离为 0）和奇数距离（初始化为 0）的节点数。 对附加到质心的每个子树执行两次 DFS。 在第一次传递期间，根据当前距质心的距离更新答案。如果这个距离是奇数，则将之前子树中距离偶数的节点数添加到答案中；否则，添加先前子树中具有奇数距离的节点数。在第二遍中，更新跟踪具有偶数和奇数距离的节点数量的变量。
然后您可以注意到质心分解是不必要的，单个 BFS 就足够了。