CF123E Maze（期望dp，树形dp，式子）-白红宇

CF123E Maze（期望dp，树形dp，式子）

阅读量：5363 次

发布时间：2019-06-15

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

题目大意：

给你一棵树，边权都是1，每一个点有一个是起点的概率和一个是终点的概率，你将以起点为根，开始在树上随机dfs，每到一个点，就会将他的所有儿子随机打乱成序列，然后按照那个随机顺序走完，直到走到终点。求dfs从起点到终点的期望长度。

其实一开始看到这个题，还是有点懵逼的啊

根据期望的线性性，我们可以通过求所有相邻点的期望，然后直接相加，得到ans

那我们可以这么考虑，对于一个点来说，假设我们要求的是从$x->y$（$y$是$x$的儿子）的期望的话，如果走到一个错的儿子，那么就需要$2*size[son]$步重新回来（相当于每条边会走两遍），而每个儿子在对应的$y$之前的概率又都是$\frac{1}{2}$（所有排列中，要不是y在前，就是那一个在前）

所以可以得知，每一个点的贡献就是$size[x]$

那么我们可以通过枚举终点，然后算其他子树的$size[x]$以及概率和，求出来他们的贡献

最后直接输出ans就好

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #define mk makr_pair#define ll long longusing namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();} while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}const int maxn = 2e5+1e2;const int maxm = 2*maxn;int point[maxn],nxt[maxm],to[maxm];double val[maxn];int size[maxn];double st[maxn],ed[maxn];int n,m;double sumst,sumed;int cnt;double ans;void addedge(int x,int y){ nxt[++cnt]=point[x]; to[cnt]=y; point[x]=cnt;}void dfs(int x,int fa){ size[x]=1; val[x]=st[x]; //cout<
            
             <<" "<
             
              <
              
               =size[x]) ans=ans+1.0*(1.0-val[x])*1.0*(1.0*n-size[x])*ed[x]; else ans=ans+val[p]*1.0*size[p]*ed[x]; // cout<
               
                <<" "<
                <<" "<
                 
                  <

转载于:https://www.cnblogs.com/yimmortal/p/10161463.html

你可能感兴趣的文章