You are given a tree with n nodes rooted at node 1, and the i-th node has a value ai. You need to assign a new value bi to each node, such that bpi≤bi for each node i and its parent pi. Output the minimum value of ∑ni=1(ai−bi)^2.
输入格式
The first line contains an integer n (1≤n≤2⋅10^5) indicating the number of nodes in the tree.
The second line contains n integers, and the i-th integer ai (0≤ai≤10^9) indicates the original value of the i-th node.
Each of the next (n−1) lines contains two integers u and v, indicating an edge between u and v.
输出格式
Output a real number indicating the minimum value of ∑ni=1(ai−bi)^2. Your answer will be considered correct if and only if the absolute or relative error of your answer to the correct answer is less than or equal to 10^(−6).