[题解] Promises I Can't Keep

· · 题解

本来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;
}