Back To School '16: Cherry Tree

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.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 N cherry patches, each with a specific number of cherries. It also has N1 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 (1N10000), C (1C105) and K (1K105), 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 ci (1ci105), representing the number of cherries on the ith patch.

The next N1 lines each contain three integers ai, bi (1ai,biN) and ki (1ki105), representing the two patches that the ith 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

Copy
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

Copy
2

Explanation for Sample Output

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.


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

      Copy
      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!