【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
",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]);
}