Back to School '16: Cherry Tree

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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

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

The next N - 1 lines each contain three integers a_{i}, b_{i} (1 \le a_{i}, b_{i} \le N) and k_{i} (1 \le k_{i} \le 10^5), representing the two patches that the 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 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 1 and 2 can be cut to obtain a portion with 12 cherries and a weight of 12. The branch connecting patches 3 and 7 can also be cut for 8 cherries and a weight of 9.


  • 3
    p1geon  commented on Feb. 25, 2019, 10:32 a.m.

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

    • 1
      pblpbl  commented on Jan. 12, 2020, 3:42 p.m. edited

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

  • -1
    Roronoa_Zoro1540  commented on Sept. 28, 2018, 10:01 a.m. edited

    can someone send help pls i AC'ed a few cases but then i got the rest wrong pls help Edit: NVM i made some stupid mistake

  • 0
    Latitude  commented on July 17, 2018, 10:43 a.m.

    Can you look my code? Maybe I didn't understand the problem right, which is common.

  • 0
    Devine  commented on April 18, 2018, 1:33 p.m.

    Help please?

    Can someone explain what I'm doing wrong?

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

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

  • 3
    septence123  commented on Jan. 8, 2017, 3: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. 8, 2017, 8:32 p.m.

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

  • 1
    septence123  commented on Jan. 8, 2017, 12:54 p.m.

    Why am I getting invalid return?

    • 2
      Kirito  commented on Jan. 8, 2017, 2:51 p.m.

      Python has a relatively small recursion limit, try

      import sys

  • 6
    Kirito  commented on Sept. 25, 2016, 8:32 p.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, 11:58 a.m.

      Reading the explanation always helps!