题目描述

有 $n+1$ 个文件夹，编号为 $0,1,2,\ldots,n$，它们成树状结构。

文件夹系统中默认的入口是文件夹 $0$，且它有一个快速访问功能，它可以存储 $k$ 个之前进行过操作的文件夹，其中 $k$ 是一个给定的正整数。具体来说，牛牛依次访问文件夹 $1$ 到 $n$，访问到文件夹 $i$ 的时候牛牛定义集合 $S_i=\{j\in\mathbf{Z} |\max(1,i-k)\le j<i\}\cup\{0\}$ 为当前的可访问集合。接下来，牛牛定义文件夹 $i$ 的可访问值为 $A_i=\sum_{j\in S_i}\text{dis}(i,j)^2$，其中 $\text{dis}(i,j)$ 是 $i$ 和 $j$ 在树上的距离，即结点 $i$ 走到结点 $j$ 需要经过的最少边数。牛牛想让你告诉他 $A_1,A_2,\ldots,A_n$ 分别是多少。

输入格式

第一行，两个正整数 $n, k$，以空格相隔。

接下来 $n$ 行，第 $i$ 行是两个整数 $u_i, v_i$，以空格相隔，表示文件夹 $u_i$ 与 $v_i$ 间存在一条无向边。

输出格式

输出 $n$ 行，第 $i$ 行输出一个整数 $A_i$。

样例

5 2
0 1
0 2
1 3
1 4
2 5

1
5
14
17
36

数据范围

• 对于 $10\%$ 的数据，$n\le 500$。
• 对于 $40\%$ 的数据，$n\le 5\times 10^3$。
• 对于全部数据，$1\le k\le n\le 2\times 10^5$，保证输入是一棵树。