You are given a hierarchical tree of items, their categories, and the subcategories of a company. Key numbers from 1 to N are assigned to the items in no specific order.



  • All products always have a key value of 1 and all the categories, subcategories, and products lie under it.
  • Products are the leaf nodes in the tree.
  • A query for discount will always be applied on the products and all products have an initial discount of 0%.

Write a program that introduces a discount D on any category, sub-category or product that helps in applying discounts and to display the discount on a particular product when queried.

Input format

  • First argument: Two dimensional array A of size 2*(N-1) where A[0][i] and A[1][i] (for all i < N) denotes a link between key(A[0][i]) and key(A[1][i]) and represents the structure of tree.
  • Second argument: Two dimensional array B of size 3*Q where B[0][i] = 0 or B[0][i] = 1 (for all i < Q) meaning thereby:
    • If B[0][i]=0, then you need to update products under key(B[1][i]) with B[2][i] percent discount.
    • If B[0][i]=1, then you need to output the discount on product B[1][i]. Ignore B[2][i] for this case.

Output format

Return an array of integers consisting of answers to each of the query corresponding to B[0][i]=1.


2 ≤ N ≤ 100000
1 ≤ Q ≤ 100000
1 ≤ A[0][i], A[1][i] ≤ N
0 ≤ B[2][i] ≤ 60 when B[0][i]=0
B[1][i] with B[0][i]=1 will only be the key of products
B[1][i] with B[0][i]=0 can be any key from [1, N]

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 PRODDISC on Interview Code Editor
Sign Up
to access hints and editorial solutions for PRODDISC


Click here to start solving coding interview questions