题目重点：从一个根的答案出发，沿父子边用n−2×子树大小更新。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 节点0..n−1，无向连通无环树，边无权；返回每个根到全部节点的边数距离之和。
- n=0且无边返回空列表；非法边、重复或不连通输入拒绝。
解题路线
- 从0构建parent/order/depth。sum(depth)是根0答案；逆序order累加子树size。使用显式遍历避免长链递归栈。
- 从u换根到子v，v子树的size[v]个节点距离各减1，其余n−size[v]个各加1，因此ans[v]=ans[u]+n−2size[v]。
- 正序遍历确保父答案已知。每个节点只参与常数次工作，避免对每个根重新BFS的O(n²)。
手动走一遍
路径0−1−2−3：ans0=6，size1=3，因此ans1=6+4−6=4；接着ans2=4、ans3=6。星形中心0、三片叶：中心距离和3，每叶5。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def distance_sums(n, edges):
if n == 0:
if edges:
raise ValueError("invalid empty tree")
return []
if len(edges) != n - 1:
raise ValueError("tree requires n-1 edges")
graph = [[] for _ in range(n)]
for u, v in edges:
if not 0 <= u < n or not 0 <= v < n or u == v:
raise ValueError("invalid edge")
graph[u].append(v)
graph[v].append(u)
parent = [-2] * n
parent[0] = -1
order, depth = [0], [0] * n
for u in order:
for v in graph[u]:
if v == parent[u]:
continue
if parent[v] != -2:
raise ValueError("cycle or repeated edge")
parent[v] = u
depth[v] = depth[u] + 1
order.append(v)
if len(order) != n:
raise ValueError("disconnected")
size = [1] * n
for v in reversed(order[1:]):
size[parent[v]] += size[v]
answer = [0] * n
answer[0] = sum(depth)
for v in order[1:]:
answer[v] = answer[parent[v]] + n - 2 * size[v]
return answer
复杂度
O(n)时间和O(n)空间，包含邻接表、parent/order/size/答案；不是仅输出数组之外O(1)。
易错点与追问
容易失分的边界
- 树公式不可直接应用一般图，因为去边后未必分成两个组件。
- 无权树的−1/+1变化，带权w时应改为w×(n−2size[v])。
继续深挖
- 节点有权重时用子树权重替代size，公式怎样写？
- 若边权动态更新，多次查询所有答案或单根答案各有什么代价？
