Grass Planting Optimization in a Tree

Farmer John has noticed that his cows often move between nearby fields. To ensure that every field has enough grass even when cows visit from neighboring fields, he wants to plant grass such that each field i can feed all cows that can reach it by crossing at most k trails.

The farm is structured as a tree with n fields (nodes) and n-1 bi-directional trails (edges) ensuring a unique path between any two fields. Field i has a weight (or number of cows) denoted by \(C(i)\). For each field i, compute the sum of weights of all fields which are at a distance of at most \(k\) trails from i.

Mathematically, for each node \(i\) in the tree, calculate:

[ m_i = \sum_{j:, d(i,j) \le k} C(j), ]

where \(d(i,j)\) is the number of trails on the unique path from i to j.

inputFormat

Input Format:

• The first line contains two integers \(n\) and \(k\) (\(1 \leq n \leq 100000\), \(1 \leq k \leq 20\)).
• The second line contains \(n\) integers, where the \(i\)th integer is \(C(i)\) (the weight or number of cows at field i).
• The next \(n-1\) lines each contain two integers \(u\) and \(v\) indicating a bi-directional trail between fields u and v.

outputFormat

Output Format:

Output a single line with \(n\) space-separated integers. The \(i\)th integer should be the computed sum \(m_i\) for field i.

sample

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

6 12 4 6 7