Back to School '16: Cherry Tree

View as PDF

Points:12 (partial)
Time limit:2.0s
Memory limit:64M
Author:

Problem type

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!

Input Specification

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 Specification

Output one integer, indicating the number of possible unique cuts that Yui can make to fulfill her requirements.

Sample Input

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


Sample Output

2


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 .

• septence123
commented on Jan. 8, 2017
Wrong ans

Got everything correct until batch 2 case 6 and batch 3 case 6, what could I be missing, code works for sample input and all of batch one.

• atarw
commented on Jan. 8, 2017

make sure your program works for certain edge cases (look at constraints)

• septence123
commented on Jan. 8, 2017
I am getting invalid Return IR?

Why am I getting invalid return?

• Kirito
commented on Jan. 8, 2017

Python has a relatively small recursion limit, try

import sys
sys.set_recursion_limit(100000000)

• Kirito
commented on Sept. 25, 2016 edited
Branches

NVM got it. Apparently when you cut, the weight of the cut one is included and that was screwing me over.