【CF123E】Maze

Portal --> cf123E

Solution

　　首先步数的话可以转化成每条边经过了几次这样来算

　　假设现在确定了起点\(S\)和终点\(T\)，我们将\(T\)看成树根，那么考虑边\((u,v)\)的经过次数可以分成下面三种情况：

　　1.\((u,v)\)在\(S\)到\(T\)的路径上，那么这条边肯定要被经过，期望为1

　　2.\((u,v)\)不在\(S\)到\(T\)的路径上，但是在\(T\)包含\(S\)的那个儿子的子树里面，那么这条边有两种情况：被经过\(2\)次或者不被经过

　　考虑一下经过顺序对贡献的影响，可以得到这样的一个结论：如果\((u,v)\)所在的“分叉”的访问顺序在\(S\)到\(T\)的路径之前，那么这条边会被经过两次，否则就一次都不会被经过。也就是：

　　该图中的橙边会被访问两次而蓝边一次都不会被访问到

　　而\((u,v)\)所在的分叉的位置只可能在直接路径的前面或者后面，所以期望是\(2*\frac{1}{2}+0*\frac{1}{2}=1\)

　　3.\((u,v)\)不在\(T\)包含\(S\)的那个儿子的子树内，也就是上图中最左边的那种边，这种边是一定不会被经过的，期望是0

　　所以，\(T\)和\(S\)确定的情况下，期望其实就是\(T\)包含\(S\)的那个儿子的子树大小

　　然后就一遍dfs，记一个\(sz[i]\)表示子树大小，\(sum[i]\)表示子树内每个点成为入口的概率总和，统计答案就好了

　　代码大概长这样

#include<iostream>

#include<cstdio>

#include<cstring>

#define db double

using namespace std;

const int MAXN=1e5+10;

struct xxx{

	int y,nxt;

}a[MAXN*2];

int h[MAXN],sz[MAXN];

db pen[MAXN],pex[MAXN],sum[MAXN];

int n,m,tot;

db ans,sumen,sumex;

void add(int x,int y);

void dfs(int fa,int x);

int main(){

#ifndef ONLINE_JUDGE

	freopen("a.in","r",stdin);

#endif

	int x,y;

	scanf("%d",&n);

	memset(h,-1,sizeof(h));

	tot=0;

	for (int i=1;i<n;++i){

		scanf("%d%d",&x,&y);

		add(x,y); add(y,x);

	}

	sumex=0; sumex=0;

	for (int i=1;i<=n;++i){

		scanf("%lf%lf",&pen[i],&pex[i]);

		sumen+=pen[i];

		sumex+=pex[i];

	}

	ans=0;

	dfs(0,1);

	printf("%.15lf\n",ans/sumen/sumex);

}

void add(int x,int y){

	a[++tot].y=y; a[tot].nxt=h[x]; h[x]=tot;

}

void dfs(int fa,int x){

	int u;

	sz[x]=1; sum[x]=pen[x];

	for (int i=h[x];i!=-1;i=a[i].nxt){

		u=a[i].y;

		if (u==fa) continue;

		dfs(x,u);

		sz[x]+=sz[u];

		sum[x]+=sum[u];

		ans+=pex[x]*sum[u]*sz[u];

	}

	ans+=pex[x]*(sumen-sum[x])*(n-sz[x]);

}

巴特西

【CF123E】Maze

Solution

最新文章

热门文章