思路是先对连接环的每条子树做树形DP再对环做一次环DP。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max(a,b) ((a)>(b)?(a):(b))
int n,f[100005][2],x,y,cnt,head[100005],ru[100005],que[100005],c[100005],tot,p[100005][2],ans;
double k;
typedef struct _edge
{
	int to,nxt;
}edge;
edge e[200005];
void addedge(int w,int h)
{
	cnt++;
	e[cnt].to=h;
	e[cnt].nxt=head[w];
	head[w]=cnt;
}
void dfs(int w,int fa)
{
	for (int i=head[w];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if (v==fa||ru[v]==2) continue;
		dfs(v,w);
		f[w][0]+=max(f[v][0],f[v][1]);
		f[w][1]+=f[v][0];
	}
}
void topo(void)
{
	int h=1,t=0;
	for (int i=1;i<=n;i++)
		if (ru[i]==1) que[++t]=i;
	while (h<=t)
	{
		int u=que[h++];
		for (int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].to;
			ru[v]--;
			if (ru[v]==1) que[++t]=v;
		}
	}
	for (int i=1;i<=n;i++)
		if (ru[i]==2)
		{
			dfs(i,0);
			c[++tot]=i;
		}
}
int main(void)
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",f[i]+1);
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);x++;y++;
		ru[x]++;ru[y]++;
		addedge(x,y);addedge(y,x);
	}
	scanf("%lf",&k);
	topo();
	//for (int i=1;i<=n;i++) printf("%d %d\n",f[i][0],f[i][1]);
	memset(p,-0x3f,sizeof(p));
	p[1][0]=f[c[1]][0];
	for (int i=2;i<=tot;i++)
	{
		p[i][0]=max(p[i-1][0],p[i-1][1])+f[c[i]][0];
		p[i][1]=p[i-1][0]+f[c[i]][1];
		//printf("%d:%d\n",p[i][0],p[i][1]);
	}
	ans=max(ans,p[tot][0]);
	ans=max(ans,p[tot][1]);
	memset(p,-0x3f,sizeof(p));
	p[1][1]=f[c[1]][1];
	for (int i=2;i<=tot;i++)
	{
		p[i][0]=max(p[i-1][0],p[i-1][1])+f[c[i]][0];
		p[i][1]=p[i-1][0]+f[c[i]][1];
		//printf("%du%d\n",p[i][0],p[i][1]);
	}
	ans=max(ans,p[tot][0]);
	printf("%.1lf\n",k*(double)ans);
	return 0;
}