Densest subtree P72633


Statement
 

pdf   zip

thehtml

Write a program that reads non empty binary trees of positive integer numbers, and for each one prints the greatest average of the elements of each subtree.

Input

Input starts with m, the number of trees that must be treated. The description of the m ‍trees follows as it is explained at the exercise , with an exception: The number of nodes is not given, because you do not need to store the trees in any vector to solve this exercise. You can suppose that any of the given trees is empty.

Output

For each tree, your program must print with four decimals the greatest average of the elements of all its subtrees.

Public test cases
  • Input

    2
    
    3 0 7 -1 4.5 -1 -1 2 -1 -1 5 4 -1 -1 7.5 6 -1 1.5 -1 -1 -1
    80 -1 50 -1 20 -1 -1
    

    Output

    5.7500
    50.0000
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++