Back to School '16: Cherry TreeView as PDF
To celebrate the start of the school year, your school has planted a cherry tree in the front yard. However, this is no ordinary cherry tree. This cherry tree has cherry patches, each with a specific number of cherries. It also has branches, each with a specific weight, connecting the patches to one another.
Yui is a big fan of cherry trees, but unfortunately does not have one of her own. She decides to make a single cut to the tree and take that part back home. She will only take home a portion that has at least cherries and a total branch weight which is at most .
Since patch is always connected to the trunk of the tree, she will never take home a portion that has patch (she isn’t crazy enough to cut down the entire tree).
Since Yui isn’t taking computer science this year, help her by writing a program to determine where to cut the tree!
The first line contains three space separated integers, , and , representing the number of patches on the tree, the number of cherries Yui wants, and the maximum weight she will take home.
The next line contains space separated integers , representing the number of cherries on the patch.
The next lines each contain three integers , and , representing the two patches that the branch connects as well as its weight.
Output one integer, indicating the number of possible unique cuts that Yui can make to fulfill her requirements.
8 5 15 1 5 9 4 3 4 8 2 1 2 3 1 3 2 2 4 5 2 5 4 3 6 6 3 7 9 3 8 1
Explanation for Sample Input
Shown below is a visualization of the tree in the sample input:
The larger number on each patch represents the number of cherries on that patch.
In this case, the branch connecting patches and can be cut to obtain a portion with cherries and a weight of . The branch connecting patches and can also be cut for cherries and a weight of .