Find the Maximum

题号：NC236495
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

A tree with $n$ vertices is a connected undirected graph with $n$ vertices and $n-1$ edges.

You are given a tree with $n$ vertices. Each vertex has a value $b_i$ . Note that for any two vertices there is exactly one single path between them, whereas a simple path doesn't contain any edge more than once. The length of a simple path is considered as the number of edges in it.

You need to pick up a simple path whose length is not smaller than $1$ and select a real number $x$ . Let $V$ be the set of vertices in the simple path. You need to calculate the maximum of $\frac{\sum_{u\in V}(-x^2+b_{u}x)}{|V|}$ .

输入描述:

The first line contains a single integer $n$ ( $2\le n \le 10^5$ ), indicating the number of vertices in the tree.

The second line contains $n$ integers $b_1,b_2,\cdots,b_n$ ( $-10^5\le b_i \le 10^5$ ), indicating the values of each vertex.

Each line in the next $n-1$ lines contains two integers $u,v$ , indicating an edge in the tree.

输出描述:

The output contains a single real number, indicating the answer.

Your answer will be accepted if and only if the absolute error between your answer and the correct answer is not greater than $10^{-4}$ .

示例1

输入

复制

2
3 2
1 2

输出

复制

1.562500