树形dp50pts求调

#include<bits/stdc++.h>
#define double long double
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	auto _u=[](char x){return x>='0'&&x<='9';};
	for(;!_u(ch);ch=='-'&&(f=-1),ch=getchar());
	for(;_u(ch);x=(x<<1)+(x<<3)+(ch^48),ch=getchar());
	return x*f;
}
inline void write(int num,bool flag=0){
	static int st[39],tp=0;
	num<0&&(putchar('-'),num=-num);
	do st[++tp]=num%10;while(num/=10);
	while(tp) putchar(st[tp--]|48);
	putchar(flag?'\n':' ');
	return;
}
template<typename...Args>
inline void write(int t,Args...args){
	return write(t),write(args...);
}
const int N=5e5+10;
double dp[N],g[N];//dp[u] 表示以 u 为根的子树的权值和
//g[u] 表示以 u 为根的整个树的权值和 
int val[N],a[N];
double ans=-1e9;
vector<int>e[N];
int rt;
inline void dfs(int u,int f){
	val[u]=(e[u].size()==1);
	for(int to:e[u])
		if(to!=f) dfs(to,u),dp[u]+=dp[to],val[u]+=val[to];
	dp[u]+=val[u]*a[u];
	return;
}
inline void dfs1(int u,int f){
	if(!f){
		g[u]=dp[u];
	}else{
		g[u]=g[f]-a[f]*val[u]+a[u]*(val[rt]-val[u]); 
		if(e[u].size()==1) g[u]-=a[u];
	} 
	for(int to:e[u])
		if(to!=f) dfs1(to,u);			
	ans=max(ans,g[u]/(val[rt]-(e[u].size()==1)));
	return;
}

int n;

signed main(){
	n=read();
	for(int i=1,x,y;i<n;++i)
		x=read(),y=read(),e[x].push_back(y),e[y].push_back(x);
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i<=n;++i) if(e[i].size()>1) rt=i;
	dfs(rt,0);
	dfs1(rt,0);
	printf("%.4Lf\n",ans);
	return(0-0);
}