g7-07689. 换根DP·每个点到所有点距离和 未做

给定一棵 $n$ 个结点的树，结点编号为 $1$ 到 $n$，每条边的长度都是 $1$。

对于每个结点 $i$，请求出它到其余 $n-1$ 个结点的距离之和。两点之间的距离定义为它们之间简单路径上的边数。

第一行一个整数 $n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示结点 $u$ 与结点 $v$ 之间有一条边。

数据保证给出的边构成一棵树。

输出一行 $n$ 个整数，第 $i$ 个整数表示结点 $i$ 到其余所有结点的距离之和。

样例 1

输入：

5
1 2
1 3
2 4
2 5

输出：

6 5 9 8 8

解释：以 $1$ 号结点为例，它到 $2,3,4,5$ 的距离依次是 $1,1,2,2$，距离和为 $6$；以 $3$ 号结点为例，距离依次是 $1,2,3,3$，距离和为 $9$。其余结点同理。

样例 2

输入：

1

输出：

0

解释：只有一个结点，它没有其余结点，距离和为 $0$。

• $1\le n\le 2\times 10^5$；
• 保证输入是一棵树；
• 答案不超过 $n^2\le 4\times 10^{10}$，可用 64 位整数存放。