Sum of Tree Nodes at a Given Depth

You are given a tree with n nodes. The tree is represented by its n-1 undirected edges and is rooted at node 1. Each node has an associated integer value. Your task is to compute the sum of the values of all nodes that are exactly at a specified depth d from the root.

A node's depth is defined as the number of edges in the unique path from the root to that node. In other words, if \(S_d\) is the set of nodes at depth \(d\), you must calculate:

[ \text{Answer} = \sum_{v \in S_d} \text{value}(v) ]

If there are no nodes at the specified depth, output 0.

inputFormat

The input is given from standard input (stdin) in the following format:

n
u1 v1
u2 v2
... (n-1 lines of edges)
val1 val2 ... valn
d

Here, n is the number of nodes in the tree. Each of the next n-1 lines contains two integers u and v, representing an edge between nodes u and v. The next line contains n integers representing the values associated with nodes 1 through n. The last line contains an integer d which is the depth at which the sum of node values is to be computed.

outputFormat

Output a single integer to standard output (stdout), which is the sum of the values of all nodes that are exactly at depth d from the root.

7
1 2
1 3
2 4
2 5
3 6
3 7
3 5 8 2 1 7 9
2

19