啊，看了眼官 sol 感觉做复杂了。

实际上我们有结论：把车和人视为一样的角色，找到重心后，答案就是 $\sum_{u \in S} dep_u$。

证明：考虑为什么一个子树里，会出现不能完全伸出去跨过重心匹配，那么必然是类似猜乘客数量 $A$ 太多，超过在这个子树外的车数量。那么外边的车数量假装是 $A - 1$，里边的车就有 $m - A + 1$，子树大小就 $> m$ 了，不符合重心定义。

这个证明对吗？好像不全有道理，但看着就很对。

然后我们直接边 $(u, v)$，然后考虑 $u$ 不是重心，$v$ 是 $u$ 的重心方向，那么枚举 $0 \le siz_u \le m$ 就可以直接计算了。

细节是 $siz_u = m$ 的部分要除二。