[Codeforces643E][DP]Bear and Destroying Subtrees-白红宇

[Codeforces643E][DP]Bear and Destroying Subtrees

阅读量：89 次

发布时间：2019-02-26

本文共 1569 字，大约阅读时间需要 5 分钟。

翻译

给你一棵初始只有根为1的树
两种操作
1 x表示加入一个新点以x为父亲
2 x表示以x为根的子树期望最深深度
每条边都有 $\frac{1}{2}$ 的概率断裂

题解

性质：我们只用考虑40层以内的节点因为深度过大的的概率太小不予考虑
设 $f [i] [j]$ 表示以i为根的子树最深深度不大于j的概率
计算答案可以直接
$\sum(f[x][i]-f[x][i-1])*i$
考虑一个点加入的影响
首先期望深度为0的话肯定是 $\frac{1}{2}$ 的儿子个数次方
一层层往上更新
第一个祖先只会影响到他的f[x][1]
第二个祖先只会影响到他的f[x][2]，大于2的我们达不到，小于2的断了我们这条边还存在影响
…
直接更新即可

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #define LL long long#define mp(x,y) make_pair(x,y)using namespace std;inline int read(){ int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar();} return x*f;}inline void write(int x){ if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar(x%10+'0');}inline void print(int x){ write(x);printf(" ");}double f[510000][45];int fa[510000],son[510000];double pow_mod(double a,int b){ double ret=1; while(b) { if(b&1)ret=ret*a; a=a*a;b>>=1; } return ret;}int main(){ int o=1; for(int i=0;i<=40;i++)f[1][i]=1; int T=read();while(T--) { int op=read(),x=read(); if(op==1) { o++;fa[o]=x;son[x]++; double lst=f[x][0]; f[x][0]=pow_mod(0.5,son[x]); for(int i=0;i<=40;i++)f[o][i]=1; for(int i=1;i<=40;i++) { int u=fa[x];if(!u)break; double gg=f[u][i]; f[u][i]/=(0.5+0.5*lst); f[u][i]*=(0.5+0.5*f[x][i-1]); lst=gg;x=u; } } else { double ans=0.0; for(int i=1;i<=40;i++)ans+=(f[x][i]-f[x][i-1])*(double)i; printf("%.10lf\n",ans); } } return 0;}

转载地址：http://gamu.baihongyu.com/

你可能感兴趣的文章

NIFI大数据进阶_FlowFile生成器_GenerateFlowFile处理器_ReplaceText处理器_处理器介绍_处理过程说明---大数据之Nifi工作笔记0019

NIFI大数据进阶_FlowFile生成器_GenerateFlowFile处理器_ReplaceText处理器_实际操作---大数据之Nifi工作笔记0020

NIFI大数据进阶_Json内容转换为Hive支持的文本格式_实际操作_02---大数据之Nifi工作笔记0032

NIFI大数据进阶_Json内容转换为Hive支持的文本格式_操作方法说明_01_EvaluteJsonPath处理器---大数据之Nifi工作笔记0031

NIFI大数据进阶_Kafka使用相关说明_实际操作Kafka消费者处理器_来消费kafka数据---大数据之Nifi工作笔记0037

NIFI大数据进阶_Kafka使用相关说明_实际操作Kafka生产者---大数据之Nifi工作笔记0036

NIFI大数据进阶_NIFI的模板和组的使用-介绍和实际操作_创建组_嵌套组_模板创建下载_导入---大数据之Nifi工作笔记0022

NIFI大数据进阶_NIFI监控功能实际操作_Summary查看系统和处理器运行情况_viewDataProvenance查看_---大数据之Nifi工作笔记0026

NIFI大数据进阶_NIFI监控的强大功能介绍_处理器面板_进程组面板_summary监控_data_provenance事件源---大数据之Nifi工作笔记0025

NIFI大数据进阶_NIFI集群知识点_认识NIFI集群以及集群的组成部分---大数据之Nifi工作笔记0014

NIFI大数据进阶_NIFI集群知识点_集群的断开_重连_退役_卸载_总结---大数据之Nifi工作笔记0018

NIFI大数据进阶_内嵌ZK模式集群1_搭建过程说明---大数据之Nifi工作笔记0015

NIFI大数据进阶_外部ZK模式集群1_实际操作搭建NIFI外部ZK模式集群---大数据之Nifi工作笔记0017

NIFI大数据进阶_实时同步MySql的数据到Hive中去_可增量同步_实时监控MySql数据库变化_操作方法说明_01---大数据之Nifi工作笔记0033

NIFI大数据进阶_实时同步MySql的数据到Hive中去_可增量同步_实时监控MySql数据库变化_操作方法说明_02---大数据之Nifi工作笔记0034

NIFI大数据进阶_离线同步MySql数据到HDFS_01_实际操作---大数据之Nifi工作笔记0029

NIFI大数据进阶_离线同步MySql数据到HDFS_02_实际操作_splitjson处理器_puthdfs处理器_querydatabasetable处理器---大数据之Nifi工作笔记0030

NIFI大数据进阶_离线同步MySql数据到HDFS_说明操作步骤---大数据之Nifi工作笔记0028

NIFI大数据进阶_连接与关系_设置数据流负载均衡_设置背压_设置展现弯曲_介绍以及实际操作---大数据之Nifi工作笔记0027

NIFI数据库同步_多表_特定表同时同步_实际操作_MySqlToMysql_可推广到其他数据库_Postgresql_Hbase_SqlServer等----大数据之Nifi工作笔记0053