3742 - 树的距离之和
Description
给定一棵无根树,假设它有 n 个节点,节点编号从 1 到 n,求 1 ~ n 这 n 个节点,到其他 n-1 个节点的距离之和。
Input
第一行包含一个正整数 n(n <= 100000),表示节点个数。

后面 (n - 1) 行,每行两个整数表示树的边。
Output
每行一个整数,第 i(i = 1, 2, ..., n)行表示所有节点到第 i 个点的距离之和。
Examples

Input

4
1 2
3 2
4 2

Output

5
3
5
5
Hint
先以 1 为根做一次 DFS,求出每个节点的子树大小 sz[u],同时算出所有节点到根的距离之和 dis[1]。

设 v 是 u 的儿子,则以 v 为根的子树中的 sz[v] 个节点到 v 的距离比到 u 少 1,其余 n-sz[v] 个节点到 v 的距离比到 u 多 1,于是

dis[v] = dis[u] + n - 2 * sz[v]

再做一次 DFS 按顺序递推即可,复杂度 O(n)。答案可能超过 int 范围,需要使用 long long。
Source
51nod 1405
Tags
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 1
通过次数 1