Nearby Cows

Farmer John has noticed that his cows often wander between nearby fields. To be ready for this, he wants every field to grow enough grass not only for the cows that start there, but also for the cows that might arrive from fields close by.

The farm has $N$ fields ($1 \le N \le 100{,}000$) connected by $N-1$ bidirectional trails. Between any two fields there is exactly one path made of trails, so the fields form a tree. Field $i$ starts with $C(i)$ cows ($0 \le C(i) \le 1000$), and a cow may wander to another field by crossing at most $K$ trails ($1 \le K \le 20$).

For every field $i$, Farmer John wants to know $M(i)$: the largest number of cows that could gather there. This equals the sum of $C(j)$ over all fields $j$ whose distance from $i$ (the number of trails on the unique path between them) is at most $K$. Given the layout of the farm and every $C(i)$, compute $M(i)$ for all fields.

• Line 1: two space-separated integers $N$ and $K$.
• Lines 2 to $N$: each line has two space-separated integers $i$ and $j$ ($1 \le i, j \le N$), meaning fields $i$ and $j$ are directly connected by a trail.
• Lines $N+1$ to $2N$: line $N+i$ contains the integer $C(i)$ ($0 \le C(i) \le 1000$).

• Lines 1 to $N$: line $i$ contains $M(i)$, the number of cows within distance $K$ of field $i$.

In the first example there are $6$ fields, with trails connecting $(5,1)$, $(3,6)$, $(2,4)$, $(2,1)$, and $(3,2)$, and field $i$ holds $C(i) = i$ cows. With $K = 2$, field $1$ can be reached within two trails by fields $1, 2, 3, 4, 5$, whose cows total $1 + 2 + 3 + 4 + 5 = 15$, so $M(1) = 15$.