5724. 树上节点距离的平方和
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 给定一棵 $n$ 个节点的树，每条边的权值为 $1$。对于树中的每个节点 $i$，你需要求出该节点与树上所有节点（包括节点 $i$ 自身）的距离的平方和。 具体来说，对于每个节点 $i \in \{1, 2, \ldots, n\}$，你需要计算： $$S\_i = \sum\_{j=1}^{n} \text{dist}(i, j)^2$$ 其中 $\text{dist}(i, j)$ 表示节点 $i$ 和节点 $j$ 之间的最短路径长度。 你需要输出所有 $S\_i$ 的值。 ## 输入格式 第一行包含一个整数 $n$，表示树的节点数。 接下来 $n-1$ 行，每行包含两个整数 $u, v$，表示节点 $u$ 和节点 $v$ 之间有一条边。 ## 输出格式 输出 $n$ 行，第 $i$ 行包含一个整数，表示 $S\_i$ 的值。 ## 输入输出样例 **输入 #1** ``` 4 1 2 2 3 3 4 ``` **输出 #1** ``` 14 6 14 ``` ## 说明/提示 ### 样例解释 给定的树是一条链：1-2-3-4。 对于节点 1： - dist(1, 1)² = 0² = 0 - dist(1, 2)² = 1² = 1 - dist(1, 3)² = 2² = 4 - dist(1, 4)² = 3² = 9 $S\_1 = 0 + 1 + 4 + 9 = 14$ 对于节点 2： - dist(2, 1)² = 1² = 1 - dist(2, 2)² = 0² = 0 - dist(2, 3)² = 1² = 1 - dist(2, 4)² = 2² = 4 $S\_2 = 1 + 0 + 1 + 4 = 6$ 对于节点 3： - dist(3, 1)² = 2² = 4 - dist(3, 2)² = 1² = 1 - dist(3, 3)² = 0² = 0 - dist(3, 4)² = 1² = 1 $S\_3 = 4 + 1 + 0 + 1 = 6$ 对于节点 4： - dist(4, 1)² = 3² = 9 - dist(4, 2)² = 2² = 4 - dist(4, 3)² = 1² = 1 - dist(4, 4)² = 0² = 0 $S\_4 = 9 + 4 + 1 + 0 = 14$ ### 数据范围 对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^5$，$1 \le u,v \le n$。