Hierarchical employee structure#1173
It is time for the annual offsite meeting at the Air Conditioning Machinery (ACM) company. All employees are excited about it. The company has a hierarchical structure led by a single CEO. Each employee reports to a manager who is one level higher in the hierarchy. Every employee has a fun index , which indicates how comfortable it is to work with them.
Alice is forming travel groups. A manager will be upset if one of their subordinates is invited to the offsite meeting, but the manager is not. Therefore, Alice must form the group so that:
1. The CEO is included in the group (this is obvious). 2. For every other employee included in the group, their manager is also included.
Alice wants to know the maximum possible average fun index for any group she can form. Can you help her?
The CEO is always employee number . The average fun index of a group is the arithmetic mean of the fun indices of all group members.
The first line contains the number of test cases .
Each test case begins with a line containing the number of employees .
The next line contains space-separated integers, where the -th number represents the fun index of employee .
The following N - 1 lines each contain two integers and , meaning that reports to (1 \le a, b \le N).
It is known that 1 \le t \le 20, 1 \le N \le 50000, 0 \le F(i) \le 10000.
For each test case, output on a separate line the maximum possible average fun index, rounded to three decimal places.
Example 1