# 题面

A tree with nn 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 \enspace (10^{-5} \leq b_i \leq 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}$$.

2
3 2
1 2


1.562500


# 题解

$t=\frac{w_1+w_2+w_3+w_4}{4}=\frac{w_1+w_2+w_3+w_4}{2}\times \frac{1}{2}=(\frac{w_1+w_2}{2}+\frac{w_3+w_4}{2})\times \frac{1}{2}=\frac{t_1+t_2}{2}$

（1）当前节点、当前节点的父节点以及当前节点的子节点，路径为父节点-当前节点-子节点

（2）当前节点和它的两个子节点，路径为子节点-当前节点-另一个子节点。

#include <bits/stdc++.h>
#define GRP int T;cin>>T;rep(C,1,T)
#define FAST ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define elif else if
#define mem(arr,val) memset(arr,val,sizeof(arr))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int n;
double w[100010];		//权值
double ans;
vector< vector<int> > e;	//vector实现邻接表
int u, v;

void dfs(int r, int pre) {
//将所有的子节点按照权值排序
sort(e[r].begin(), e[r].end(), [](int a, int b)->bool{
return w[a] > w[b];
});
//如果子节点有至少两个，就考虑子节点-当前节点-子节点这样的路径（以无向树存储，DFS只是视作有向树，因此需要排除掉父节点）
if (e[r].size() > 2 || (pre < 1 && e[r].size() > 1)) {
int cnt = 0, flag = 0;
double cur = w[r];
//挑权值最大的两个节点
while (cnt != 2) {
//如果其中一个是父节点
if (e[r][flag] == pre) {
++flag;
continue;
}
cur += w[e[r][flag]];
++flag;
++cnt;
}
cur /= 3;
ans = max(ans, cur * cur / 4);	//更新答案
cnt = 0, flag = e[r].size() - 1;
cur = w[r];
//挑权值最小的两个节点
while (cnt != 2) {
if (e[r][flag] == pre) {
--flag;
continue;
}
cur += w[e[r][flag]];
--flag;
++cnt;
}
cur /= 3;
ans = max(ans, cur * cur / 4);
}
for (int i : e[r]) {
if (i == pre) {
continue;	//不能回头
}
//不是起始节点的情况下，考虑父节点-当前节点-子节点的路径
if (pre > 0) {
double t = (w[pre] + w[r] + w[i]) / 3;
ans = max(ans, t * t / 4);	//更新答案
}
dfs(i, r);	//继续搜索
}
}
int main() {
FAST
cin >> n;
e.resize(n + 1);
ans = 0;
rep(i, 1, n) {
cin >> w[i];
}
rep(i, 1, n - 1) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
double t = (w[u] + w[v]) / 2;  //长度为1的边读入时就可以进行处理
ans = max(ans, t * t / 4);
}
dfs(1, -1);	//指定起始节点为第一个节点，并且指定其父节点不存在
cout << fixed << setprecision(6) << ans << endl;
return 0;
}

/*
_           _    _            _
/\   | |         | |  | |          (_)
/  \  | | _____  _| |__| | ___  _ __ _ _ __   __ _
/ /\ \ | |/ _ \ \/ /  __  |/ _ \| '__| | '_ \ / _ |
/ ____ \| |  __/>  <| |  | | (_) | |  | | | | | (_| |
/_/    \_\_|\___/_/\_\_|  |_|\___/|_|  |_|_| |_|\__, |
__/ |
|___/
*/
`

2 total views,  1 views today