自动搬运

查看原文

来自洛谷，原作者为

	UltiMadow Well I do.

搬运于2025-08-24 22:21:52，当前版本为作者最后更新于2020-04-23 21:48:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本来T2是个DS题的，但是发现撞题之后就换上了这一道

先来看部分分吧

subtask 0

简单暴力，以每个点为根做一遍dp

subtask 1

链的情况大概可以前缀和乱搞，不多说了

正解

换根dp（个人感觉不难想吧）

令 $cnt_u$ 为以 $u$ 为根节点的子树中叶子节点的个数

设 $g_u$ 为以 $u$ 为根节点的期望值 $\times cnt_u$，这里乘是为了精度不要有误差

设 $f_u$ 为以 $u$ 为根节点的整个树的期望值乘以 $u$ 为根节点的整棵树中的叶子节点个数

第一次dfs预处理出 $g$ 和 $cnt$

显然有：
当 $u$ 为叶子节点时 $cnt_u=1$，$g_u=val_u$
当 $u$ 为非叶子节点时 $cnt_u=\sum_{v\in son_u}cnt_v$，$g_u=val_u\times cnt_u+\sum_{v\in son_u}g_v$

第二次dfs计算 $f$

显然有：
当 $u$ 为根节点时 $f_{u}=g_{u}$
当 $u$ 为叶子节点时 $f_u=f_{fa}-val_u-val_{fa}+(cnt_{root}-1)\times val_u$
整理得：$f_u=f_{fa}-val_{fa}+(cnt_{root}-2)\times val_u$
当 $u$ 为非叶子节点时 $f_u=f_{fa}-g_u-cnt_u\times val_{fa}+g_u+(cnt_{root}-cnt_u)\times val_u$
整理得：$f_u=f_{fa}-cnt_u\times val_{fa}+(cnt_{root}-cnt_u)\times val_u$

code:

#include<bits/stdc++.h>
#define int long long
#define MAXN 500010
using namespace std;
int n,rt;
double val[MAXN];
double f[MAXN],g[MAXN];
int cnt[MAXN],lef[MAXN];
struct Node{int to,next;}Edge[MAXN<<1];
int Head[MAXN],cnt_Edge;
void Add_Edge(int u,int v){Edge[++cnt_Edge]=(Node){v,Head[u]};Head[u]=cnt_Edge;}
void dp1(int u,int fa)
{//第一次dfs
	for(int i=Head[u];i;i=Edge[i].next)
	{
		int v=Edge[i].to;
		if(v==fa)continue;
		dp1(v,u);cnt[u]+=cnt[v];
		g[u]+=g[v];
	}
	g[u]+=val[u]*cnt[u];
	if(!cnt[u])g[u]=val[u],cnt[u]=1,lef[u]=1;
}
void dp2(int u,int fa)
{//第二次dfs
	for(int i=Head[u];i;i=Edge[i].next)
	{
		int v=Edge[i].to;
		if(v==fa)continue;
		if(lef[v])f[v]=f[u]-val[u]+val[v]*(cnt[rt]-2);
		else f[v]=f[u]-val[u]*cnt[v]+val[v]*(cnt[rt]-cnt[v]);
		dp2(v,u);
	}
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<n;i++)
	{
		int u,v;scanf("%lld%lld",&u,&v);
		Add_Edge(u,v);Add_Edge(v,u);
	}
	for(int i=1;i<=n;i++)scanf("%lf",&val[i]);
	for(int i=1;i<=n;i++)
		if(Edge[Head[i]].next!=0){rt=i;break;}//找非叶子节点为根
	dp1(rt,0);f[rt]=g[rt];dp2(rt,0);
	double ans=-99999999999;
	for(int i=1;i<=n;i++)ans=max(ans,f[i]/(cnt[rt]-lef[i]));//计算期望
	printf("%.4lf",ans);
	return 0;
}