3693: 快速访问(第四轮03)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：4
解决：1
题目描述
有n + 1个文件夹，编号为0,1,2, . . . n，它们成树状结构。
文件夹系统中默认的入口是文件夹0，且它有一个快速访问功能，它可以存储k个 之前进行过操作的文件夹，其中k是一个给定的正整数。具体来说，牛牛依次访 问文件夹1到n，访问到文件夹i的时候， 牛牛定义集合si = {j ∈ ℤ ∣ max (1, i − k) ≤ j < i} ∪ {0}为当前的可访问集合。接下来，牛牛定义文件夹i的可访问值为 Ai = Σj∈si dis(i,j)2，其中dis(i,j) 是i和j在树上的距离，即结点i走到结点j需要经 过的最少边数。牛牛想让你告诉他A1, A2, . . . , An 分别是多少。
输入
第一行，两个正整数n, k ，以空格相隔。
接下来n行，第i行是两个整数ui, vi，以空格相隔，表示文件夹ui 与vi 间存在一条 无向边。
输出
输出n行，第i行输出一个整数Ai 。
样例输入 复制
5 2
0 1
0 2
1 3
1 4
2 5
样例输出 复制
1
5
14
17
36提示
【数据范围】
对于 10%数据，满足1 ≤ k ≤ n ≤ 500 。
对于 40%数据，满足1 ≤ k ≤ n ≤ 5000。
对于 100%数据，满足1 ≤ k ≤ n ≤ 200000,0 ≤ ui, vi ≤ n，保证输入为一棵树。