问题4143--Tree Query

4143: Tree Query

[命题人 : ]
时间限制 : 1.000 sec  内存限制 : 128 MB

提交

题目描述

     Now we have a tree which is rooted at node 1, and the tree has N nodes (N <= 100000), then I will tell you a integer w and the value of each node, 

the value will be a postive integer no more than 10^9. Now I will tell you  each edge of the tree. For each node u, I want you to select the most nodes from the subtree which is rooted at u, that the total value of the selected nodes would not be more than w. I think you are smart enough to tell me the number for each node.

输入

     There are multiple data sets, process the program to the end of file. 

The first line are two integers N,W(N <= 10^5,w <= 10^9), the second line will contain N integers vi,(1 <= i <= N, 1 <= vi <= 1000, vi is the value of node i), then there will be followed N-1 lines, each line are two integers u and v, denotes the edge of the tree.

输出

     For each data set please output a line with N integers separated by one space, no space after the last integer, the number of most nodes can be selected from each subtree of the corresiponding node such that total value  those nodes are no more than w.

样例输入 Copy 

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

样例输出 Copy 

2 1 1 1 0

来源/分类

 
提交