Codeforces 123E Maze(树形DP+期望)

forever97 posted @ 2016年10月20日 00:05 in 算法-树形DP with tags 树形DP 期望 , 639 阅读

 

【题目链接】 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;
} 
Jai Verge 说:
2018年7月15日 15:32

Community and the programming of the software with the all counting products on the codeforces are now begun. On the Russia the time of the websites are on the bestessays and for the programming of the very generations.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter