树链剖分

题目描述 你有一棵�个节点的树。你能将树划分成若干条链。

一个有根树的树链剖分为将整棵树划分成若干条从一个点到这个点的某个祖先（包 括本身）的链，并且这些链没有公共点。如果一条边在某条链上，即这条边的两个 端点在同一条链上，那么这条边为重边，否则为轻边。

一个树链剖分的代价为所有点对的路径上轻边的个数之和。这里将 �, � 和 �, � 当 成同一个点对。一个有根树的最优树链剖分为所有方案中代价最小的方式。

对于一棵无根树，你想知道以每个点为根对应的有根树的最优树链剖分的代价。

输入格式 第一行一个整数�，表示树的节点个数。

接下来� − 1 行，每行包含两个正整数，�, �，表示�和�在树上有边相连。

输出格式 输出�行，第�行表示第�个点为根对应的有根树的最优树链剖分的代价。

样例输入 1 7 4 6 5 4 2 5 1 3 7 4 1 7

样例输出 1 12 6 6 16 12 10 16

样例输入输出 2 见下发文件。

数据规模 共 10 个测试点。 测试点 1,2,3 满足� ≤ 15。

测试点 4,5,6 满足� ≤ 1000。

对于所有数据，满足 1 ≤ � ≤ 105 。