Back To School '16: Cherry Tree

View as PDF

Submit solution

All submissions

Best submissions

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

atarw

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 $N$ ~N~ cherry patches, each with a specific number of cherries. It also has $N-1$ ~N-1~ 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 $C$ ~C~ cherries and a total branch weight which is at most $K$ ~K~.

Since patch $1$ ~1~ is always connected to the trunk of the tree, she will never take home a portion that has patch $1$ ~1~ (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, $N$ ~N~ $(1 \le N \le 10\,000)$ ~(1 \le N \le 10\,000)~, $C$ ~C~ $(1 \le C \le 10^5)$ ~(1 \le C \le 10^5)~ and $K$ ~K~ $(1 \le K \le 10^5)$ ~(1 \le K \le 10^5)~, 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 $N$ ~N~ space separated integers $c_i$ ~c_i~ $(1 \le c_i \le 10^5)$ ~(1 \le c_i \le 10^5)~, representing the number of cherries on the $i^{th}$ ~i^{th}~ patch.

The next $N-1$ ~N-1~ lines each contain three integers $a_i$ ~a_i~, $b_i$ ~b_i~ $(1 \le a_i, b_i \le N)$ ~(1 \le a_i, b_i \le N)~ and $k_i$ ~k_i~ $(1 \le k_i \le 10^5)$ ~(1 \le k_i \le 10^5)~, representing the two patches that the $i^{th}$ ~i^{th}~ 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

Explanation for Sample Output

Shown below is a visualization of the tree in the sample input:

$\text{[math]}$

The larger number on each patch represents the number of cherries on that patch.

In this case, the branch connecting patches $1$ ~1~ and $2$ ~2~ can be cut to obtain a portion with $12$ ~12~ cherries and a weight of $12$ ~12~. The branch connecting patches $3$ ~3~ and $7$ ~7~ can also be cut for $8$ ~8~ cherries and a weight of $9$ ~9~.

Comments

5

p1geon commented on Feb. 25, 2019, 3:32 p.m.

it's a good thing to know that nodes will always be the child of a node with a smaller number

3

pblpbl commented on Jan. 12, 2020, 8:42 p.m. ← edited →

this is actually helpful ngl (should be in the problem statement)

3

Ninjaclasher commented on Aug. 7, 2017, 11:14 p.m.

Is it guaranteed that the farther away the patch is from patch 1, the larger the patch index?

2

septence123 commented on Jan. 8, 2017, 8:47 p.m.

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.

2

atarw commented on Jan. 9, 2017, 1:32 a.m.

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

0

septence123 commented on Jan. 8, 2017, 5:54 p.m.

Why am I getting invalid return?

2
Kirito commented on Jan. 8, 2017, 7:51 p.m. ← edited →
Python has a relatively small recursion limit, try

import sys sys.setrecursionlimit(100000000)

6

Kirito commented on Sept. 26, 2016, 12:32 a.m. ← edited →

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

1

14CF208B commented on March 28, 2019, 3:58 p.m.

Reading the explanation always helps!