#4933. 妙

题目描述

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  

数据范围与提示