P6554 Promises I Can't Keep
题解
看题解都有些做烦了，就来发一篇。
换根 dp。第一遍 dfs 处理出 \(Lef_u\) 表示 \(u\) 子树内的叶子个数（包含自己），然后求出以 \(1\) 为根时的答案 \(\sum Lef_u*val_u\)，注意特判根为叶子的情况。
第二遍 dfs 大力换根就好了，从根 \(u\) 换到根 \(v\) 时真正有变化的只有 \(Lef_u\) 和 \(Lef_v\)，于是可以直接修改再回溯，同步更新从根到所有叶子的权值和，然后对于每一个根，答案就是好计算的。
代码：
/*
* @Author: operator_
* @Date: 2023-11-23 08:55:31
* @Last Modified by: operator_
* @Last Modified time: 2023-11-23 09:34:33
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int rd() {
int s=0,m=0;char ch=getchar();
while(!isdigit(ch)) {if(ch=='-')m=1;ch=getchar();}
while( isdigit(ch)) s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return m?-s:s;
}
int n,a[500005],d[500005],Lef[500005],Sl,f[500005],Sum;
double Ans=-1e12;
int h[500005],Cnt;
struct Graph {int u,v,Nxt;} e[1000005];
void Add(int u,int v) {e[++Cnt]={u,v,h[u]},h[u]=Cnt;}
void Dfs1(int u,int p) {
if(d[u]==1) Lef[u]=1;
for(int i=h[u];i;i=e[i].Nxt) {
int v=e[i].v;
if(v==p) continue;
Dfs1(v,u);
Lef[u]+=Lef[v];
}
Sum+=Lef[u]*a[u];
}
void Dfs2(int u,int p) {
if(d[u]==1) Ans=max(Ans,(Sum-a[u])*1.0/(Sl-1));
else Ans=max(Ans,Sum*1.0/Sl);
for(int i=h[u];i;i=e[i].Nxt) {
int v=e[i].v;
if(v==p) continue;
Sum-=Lef[u]*a[u]+Lef[v]*a[v];
Lef[u]=Sl-Lef[v];
Lef[v]=Sl;
Sum+=Lef[u]*a[u]+Lef[v]*a[v];
Dfs2(v,u);
Sum-=Lef[u]*a[u]+Lef[v]*a[v];
Lef[v]=Sl-Lef[u];
Lef[u]=Sl;
Sum+=Lef[u]*a[u]+Lef[v]*a[v];
}
}
signed main(){
cin>>n;
for(int i=1;i<n;i++) {
int u=rd(),v=rd();
Add(u,v),Add(v,u);
d[u]++,d[v]++;
}
for(int i=1;i<=n;i++)
a[i]=rd();
Dfs1(1,0);
Sl=Lef[1];
Dfs2(1,0);
printf("%.4lf",Ans);
return 0;
}