首页 > 代码库 > Codeforces 123E Maze(树形DP+期望)
Codeforces 123E Maze(树形DP+期望)
【题目链接】 http://codeforces.com/problemset/problem/123/E
【题目大意】
给出一棵,给出从每个点出发的概率和以每个点为终点的概率,求出每次按照dfs序从起点到达终点的期望。
【题解】
首先对于期望计算有X(x,y)=X(x)*X(y),所以对于每次dfs寻路只要求出其起点到终点的期望步数,乘上起点的概率和终点的概率即可。对于一个固定起点和终点的dfs寻路,我们可以发现如果一个点在必要路径上,那么这条路被走过的期望一定为1,如果不在必要路线上,那么走过的次数为0或者2,期望也为1,那么就是和x相连且在x到达y之前能到达的点连成的连通块大小减一就是x到y的dfs寻路期望长度。
为更方便地处理问题,首先我们将无根树转化为有根树,我们发现如果起点是终点的子节点,那么连通块的大小均为size[终点],如果不是,则连通块的大小一定为n-size[终点]+1,所以我们可以用树形DP,来统计这些信息,同时在访问每个节点的时候计算。
【代码】
#include <cstdio>#include <algorithm>#include <vector>using namespace std;const int N=300000;int st[N],en[N],n,x,y,size[N];double ans=0,sst,sen;vector<int> v[N];void dfs(int x,int fx){ size[x]=1; for(int i=0;i<v[x].size();i++){ if(v[x][i]!=fx){ dfs(v[x][i],x); size[x]+=size[v[x][i]]; st[x]+=st[v[x][i]]; ans+=1.0*st[v[x][i]]*size[v[x][i]]*en[x]; } }ans+=(sst-st[x])*(n-size[x])*en[x];} int main(){ scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d",&x,&y); v[x].push_back(y); v[y].push_back(x); }for(int i=1;i<=n;i++){ scanf("%d%d",st+i,en+i); sst+=st[i]; sen+=en[i]; }dfs(1,-1); printf("%.11f\n",ans/sst/sen); return 0;}
Codeforces 123E Maze(树形DP+期望)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。