2021 ICPC 昆明站 F - Find the Maximum 题解

#include<bits/stdc++.h>
using namespace std;
#ifdef SteinsGate0
#include<SteinsGate0.h>
#else
#define dbg(x)
#define look(x,...)
#define pr(x,...)
#define yes
#define no
#define IN    freopen("input.txt","r",stdin)
#define OUT   freopen("output.txt","w",stdout)
#endif
#define ll __int128
#define GET   freopen(".in","w",stdout)
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define mt mt19937 mt_rand(time(0))
#define cx(x) cout << (x) << " "
#define cl cout << endl
#define cxl(x) cout << (x) << endl
#define YES cout << "YES\n"
#define NO cout << "NO\n"
#define fl fflush(stdout)
#define inv(x) qsm(x,mod-2,mod)
#define ceil(x,y) (long long)(((x)+(y)-1)/(y))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const double PI=acos(-1.0);constexpr double eps=1e-6;constexpr long long inf=LLONG_MAX/10;constexpr int mod=998244353;constexpr int maxn=2e6+6;
long long n,m,k,ans,_=1,a[maxn];
int sgn(double a,double b){ if(abs(a-b)<eps) return 0; return a>b?1:-1; }
long long qsm(long long a,long long b,long long p=inf){ long long ret=1; while(b){ if(b&1) ret*=a,ret%=p; b/=2,a*=a,a%=p; } return ret; }
//bool isp[maxn]; int prime[maxn]; int euler[maxn]; void inip(){ euler[1]=1,isp[1]=true; for(int i=2;i<maxn;i++){ if(!isp[i]){ prime[++prime[0]]=i; euler[i]=i-1; } for(int j=1;j<=prime[0]&&i*prime[j]<maxn;j++){ isp[i*prime[j]]=true; if(i%prime[j]==0){ euler[i*prime[j]]=euler[i]*prime[j]; break; } euler[i*prime[j]]=euler[i]*euler[prime[j]]; } } }
//long long fac[maxn],invf[maxn]; void inif(){ fac[0]=fac[1]=invf[0]=invf[1]=1; for(int i=2;i<maxn;i++) fac[i]=fac[i-1]*i%mod; invf[maxn-1]=qsm(fac[maxn-1],mod-2,mod); for(int i=maxn-2;i>=1;i--) invf[i]=invf[i+1]*(i+1)%mod; } long long C(long long n,long long m){ return n<m?0:fac[n]*invf[m]%mod*invf[n-m]%mod; }
struct Edge{ int from,v; }e[maxn<<1]; int ent=0; int head[maxn]; void init(){ ent=0; memset(head,-1,sizeof(head)); } void add(int u,int v){ e[ent].from=head[u]; e[ent].v=v; head[u]=ent++; }
long long t[maxn];
void up(pair<long long,long long>& now,long long x,int flag){
	dbg(x);
	x*=flag;
	if(x>now.second){
		now.second=x;
		if(x>now.first) swap(now.first,now.second);
	}
}
int main(){
	init();
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<n;i++){
		int u,v;
		cin >> u >> v;
		add(u,v);	
		add(v,u);
	}
	pair<long long,long long> maxx,minn;
	double ans=0;
	for(int i=1;i<=n;i++){
		int cnt=0;
		maxx={-inf,-inf},minn={-inf,-inf};
		for(int j=head[i];~j;j=e[j].from){
			cnt++;
			up(maxx,a[e[j].v],1);
			up(minn,a[e[j].v],-1);
		}
		look(maxx.first,maxx.second);
		look(minn.first,minn.second);
		dbg(cnt);
		long long b1=a[i]+maxx.first;
        long long b2=a[i]-minn.first;
        long long b=max(b1*b1,b2*b2);
        ans=max(ans,b/16.0);
		if(cnt>1){
			long long b1=a[i]+maxx.first+maxx.second;
			long long b2=a[i]-minn.first-minn.second;
			long long b=max(b1*b1,b2*b2);
			 ans=max(ans,b/36.0);
		}
	} printf("%.6f",ans);
}