Harvesting Apples at Tree Nodes Within Distance k

There is a tree $T$ with $n$ vertices and $n-1$ edges. The vertices are numbered from 0 to $n-1$, and vertex 0 is the root. Every edge has length 1. Each vertex of $T$ has either 0 or 1 apple. You want to harvest the apples on the nodes whose distance from the root node is at most $k$. Print the number of apples you can harvest.

The first line contains the number of vertices $n$ and the integer $k$, separated by a space.

From the second line onward, the next $n-1$ lines describe the edges. Each line contains one edge, given as a parent vertex number $p$ and a child vertex number $c$, separated by a space.

The next line contains $n$ integers, separated by spaces, that give the apple count of each vertex from 0 to $n-1$. The $i$-th number is the number of apples on vertex $i-1$. Each number is 0 or 1.

Print the number of apples you can harvest on the first line.

• $2 \le n \le 100{,}000$
• $0 \le p, c \le n-1$, $p \ne c$
• The graph formed by the edges is a tree.
• $0 \le k \le n-1$
• The number of apples on each vertex is 0 or 1.