P1453 城市环路
本质上其实就是一个基环树上的没有上司的舞会
但是由于太蒻了第一次接触。。。还是看了题解
https://www.luogu.com.cn/blog/Zctoylm/solution-p1453
#include<bits/stdc++.h>
#define for1(i,a,b) for(int i = a;i<=b;i++)
#define ll long long
#define mp(a,b) make_pair(a,b)
using namespace std;
int n,p[100005],fa[100005],s,t;
struct node{
int to,nex;
}e[100005<<1];
int cnt,hd[100005];
double f[100005][2],k,ans=0;;
void ru(int u,int v)
{
e[++cnt].to=v;
e[cnt].nex=hd[u];
hd[u]=cnt;
}
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
void dfs(int x,int fa)
{
f[x][1]=p[x];
f[x][0]=0;
for(int i=hd[x];i;i=e[i].nex)
{
int v=e[i].to;
if(v==fa)continue;
dfs(v,x);
f[x][0]+=max(f[v][0],f[v][1]);
f[x][1]+=f[v][0];
}
}
int main()
{
cin>>n;
for1(i,1,n)cin>>p[i],fa[i]=i;
int u,v;
for1(i,1,n)
{
cin>>u>>v;
u++,v++;
if(find(u)==find(v))
{
s=u,t=v;
continue;
}
ru(u,v);
ru(v,u);
fa[find(v)]=find(u);
}
scanf("%lf",&k);
dfs(s,0);
ans=f[s][0];
dfs(t,0);
ans=max(ans,f[t][0]);
printf("%.1lf\n",ans*k);
return 0;
}