自动搬运

查看原文

来自洛谷，原作者为

	龙神哈迪斯 **

搬运于2025-08-24 21:25:15，当前版本为作者最后更新于2018-08-15 14:21:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

放在前面的话

那个，楼下的$dfs$找环的确有问题，就在讨论区的那组数据可以把它成功$Hack$掉

然后几篇题解似乎都是基环树？这么高级的东西我还不会啊

大多人没把$dp$定义式讲清楚，然我们这种$小蒟蒻$很尴尬啊，于是我决定献丑一发

然后这题其实是我在图论里找的，结果莫名跑出一道树形dp来，可能Luogu知道我的树形dp太菜了，然后推荐的???

欢迎大家来$Hack$

题目大意

给你一棵树，点有点权，强制要求一条边只能选一个点，并且还额外命令$(S,T)$也不能同时选，求满足条件下的最大贡献

Sol

这不是摆明了那你用树形dp切掉的节奏吗？

设$f[u][0/1]$表示以$u$为根的字树，$u$点选或不选的最大贡献

然后转移比较显然，

1.如果$u$点要选，则它所有的儿子都不能选

2.如果$u$点不选，那么它的儿子可以选也可以不选

所以转移式就是

然后考虑最后的统计答案

以$S$，$T$两点分别做一次$dp$，然后在$f[S][0],f[T][0]$中取较大值，这样就能保证$S,T$不可能同时被选了

code

然后就是愉快的上代码环节了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int _=100005;
inline int read()
{
	char ch='!';int z=1,num=0;
	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')z=-1,ch=getchar();
	while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
	return z*num;
}
int n,p[_],fa[_],S,T;
struct ed{int to,next;}e[_<<1];
int cnt,head[_];
double f[_][2];
void link(int u,int v){e[++cnt]=(ed){v,head[u]};head[u]=cnt;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void dfs(int u,int fa)
{
	f[u][1]=p[u];f[u][0]=0;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa)continue;
		dfs(v,u);
		f[u][0]+=max(f[v][0],f[v][1]);
		f[u][1]+=f[v][0];
	}
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)p[i]=read(),fa[i]=i;
	for(int i=1;i<=n;++i)
	{
		int u=read()+1,v=read()+1;
		if(find(u)==find(v)){S=u,T=v;continue;}
		link(u,v);link(v,u);fa[find(v)]=find(u);
	}
	double k,ans=0;
	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;
}