#4933. 妙

内存限制:256 MiB 时间限制:10 Sec

题目描述

Mr.董已经成长为一个地区的领袖,真是妙啊。董所在的地区由n个小区域构成,这些小区域构成了一棵树,每个小
区域都有一个重要程度,一个连通块的重要程度为其包含的小区域重要程度之和。现在董想进行一些调查,由于1
号区域是领袖重地,他问你包含1号的重要程度前k小的连通块重要程度分别是多少。如果连通块数不足k则全部输
出。

输入格式

第一行两个整数n和k。
第二行n个整数表示每个区域的重要程度。
接下来n-1行每行两个整数表示一条边。

输出格式

输出k行每行一个整数,第i行表示包含1号的重要程度第i小的连通块的重要程度。
如果连通块数不足k个,则不必输出k行,只要全部输出即可。具体可见样例。
100%的数据n,k<=100000,区域的重要程度的绝对值小于1,000,000,000。

样例

样例输入


			
5 100
1 2 -3 1 2
1 2
2 3
2 4
3 5

样例输出


			
0
1
1
2
3
3
4

数据范围与提示