记录

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int a[maxn];
bool vis[maxn];
vector<int>ve[maxn];
int book[maxn];
int dp1[maxn];
int dp2[maxn];
int n;
int ui1=1,ui2;
void pps(){
	queue<int>q;
	for(int i=1;i<=n;i++){
		if(book[i]==1){
			q.push(i);
		}
	}
	while(!q.empty()){
		int o=q.front();
		q.pop();
		for(int i=0;i<ve[o].size();i++){
			if(vis[ve[o][i]]){
				continue;
			}
			book[ve[o][i]]--;
			book[o]--;
	    	if(book[ve[o][i]]==1){
	    		q.push(ve[o][i]);
			}
		}
		vis[o]=1;
	}
	for(int i=1;i<=n;i++){
		if(vis[i]){
			continue;
		}
		for(int j=0;j<ve[i].size();j++){
			if(vis[ve[i][j]]){
				continue;
			}
			//cout<<i<<"   "<<ve[i][j]<<endl;
		}
	}
	return ;
}
void dfs(int op,int fa){
	//cout<<"op: "<<op<<" fa: "<<fa<<endl;
	dp1[op]=a[op];
	for(int i=0;i<ve[op].size();i++){
		if(fa==ve[op][i]||(ve[op][i]==ui1&&op==ui2)||(ve[op][i]==ui2&&op==ui1)){
			continue;
		}
		dfs(ve[op][i],op);
		dp1[op]+=dp2[ve[op][i]];
		dp2[op]+=max(dp1[ve[op][i]],dp2[ve[op][i]]);
	}
	return ;
}
int main(){
	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;
		ve[u+1].push_back(v+1);
		ve[v+1].push_back(u+1);
		book[v+1]++;
		book[u+1]++;
	}
	pps();
	ui2=n;
	while(vis[ui1]){
		ui1++;
	}
	while(vis[ui2]){
		ui2--;
	}
	int ans;
	double k;
	cin>>k;
	//cout<<"ui1: "<<ui1<<" ui2: "<<ui2<<endl; 
	dfs(ui1,-5);
	ans=dp2[ui1];
	for(int i=0;i<=maxn-5;i++){
		dp1[i]=0;
		dp2[i]=0;
	}
	dfs(ui2,-5);
	ans=max(ans,dp2[ui2]);
	cout<<fixed<<setprecision(1)<<ans*k;
	return 0;
}
/*
8
3 3 2 2 2 4 5 4
0 1
1 2
2 3
3 0
5 0
6 5
0 7
0 8
1.11111

15.6
*/