Longest path in a subtree

You are given a tree with A nodes. You are given two integer array B and C which represents an edge i.e.
there is an edge from node B[i] to C[i].You need to tell the count of subtrees such that the length of the longest path in the subtree is at most D.

Since this count may be very large. Return the count of such subtree modulo (109+7).



Input Format

The first argument is an integer A.
The second argument is an array of integers B.
The Third argument is an array of integers C.
The Fourth argument is an integer D.

Output Format

Return the count of subtrees such that the length of the longest path in the subtree is at most D modulo (10^9+7).

Constraints

2 <= A <= 60
1 <= B[i] , C[i] <= A 
B[i]!=C[i]
1 <= D < A

For Example

Input 1:
    A = 3
    B = [1, 2]
    C = [2, 3]
    D = 1
    
       2
      / \
     1   3

Output 1:
    5
    subtrees with atmost longest path equal to 1 : 1, 2, 3, (1,2) , (2,3)

Input 2:
    A = 6
    B = [1, 2, 3, 3, 4] 
    C = [2, 3, 4, 5, 6]
    D = 3 
Output 2:
    23
NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
Start solving Longest path in a subtree on Interview Code Editor
Sign Up
to access hints and editorial solutions for Longest path in a subtree

Discussion


Loading...
Click here to start solving coding interview questions