CodeForces#123 E.Maze

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

#.Maze

题面

A maze is represented by a tree (an undirected graph, where exactly one way exists between each pair of vertices). In the maze the entrance vertex and the exit vertex are chosen with some probability. The exit from the maze is sought by Deep First Search. If there are several possible ways to move, the move is chosen equiprobably. Consider the
following pseudo-code:

DFS(x)
    if x == exit vertex then
        finish search
    flag[x] <- TRUE
    random shuffle the vertices' order in V(x) // here all permutations have equal probability to be chosen
    for i <- 1 to length[V] do
        if flag[V[i]] = FALSE then
            count++;
            DFS(y);
    count++;

$V(x)$ is the list vertices adjacent to $x$. The $flag$ array is initially filled as FALSE. $DFS$ initially starts with a parameter of an entrance vertex. When the search is finished, variable $count$ will contain the number of moves.

简要翻译

一棵 $n$ 个点的树，起点和终点随机选取。运行如下程序， $V(x)$ 是与 $x$ 相邻的顶点列表，最初 $flag$ 数组为 $false$,$DFS$ 的参数是起点，你要求 $count$ 的期望值。

~~（自己给洛谷的翻译跪着也要搬过来）~~

Input

第一行一个数 $n$，表示个节点。
接下来 $n-1$ 行，每行两个数$(u,v)$,表示有一条从 $u$，到$v$的无向边。
然后是$n$行，每行描述一个节点表示该节点被选为进入点的 $x$ 和该节点被选为离开的 $y$ 。

此处的x和y用于求每个点被选为进入点的概率和被选为离开点的概率，即：
$p[x]=\frac{x}{sum(x)}$,$p[y]=\frac{y}{sum(y)}$.

Output

一个实数表示$count$的期望。

（误差允许范围$\le 10^9$）

Sample Input 1

1 2

0 1

1 0

Sample Output 1

1.00000000000000000000

Sample Input 2

1 2

1 3

1 0

0 2

0 3

Sample Output 2

2.00000000000000000000

Sample Input 3

1 2

1 3

2 4

2 5

3 6

3 7

1 1

Sample Output 3

4.04081632653

Hint

$n<10^5$

突然发现这是一道比较经典的题，讲课时被提到了好几次，我~~神奇般~~的给了某谷一个~~强有力的~~翻译，~~不扯了（竟然知道在扯）~~。

看过随机树那篇题解的都知道。~~（又骗人去刷博客访问量）~~

~~(原谅我直接截图)~~

题面非常的显然，那么我们先求出每一棵子树的大小，设一个$P_x$表示当$x$被当做离开点时，从别的子树出发到达他的概率。

使用$DFS$求出子树大小，同时求出该子树中每个点被选为$Enter$的概率和，并且枚举每个点作为$Exit$。

用之前的那个公式求出以该节点为根节点的子树出发到该节点的期望以及从别的子树出发到该节点的期望。

设这个点为$x$，对于它以外的子树将其看作$x$的另一子树。

这样一设计，这题似乎就可以~~Van爆了~~。

Code

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,w=0;
	char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return w? -x:x;
}
int n;
vector<int> v[100010];
int sz[100010],fa[100010];
double P_in[100010],P_out[100010],res,Sin,Sout;
bool vis[100010];
#define Size_ v[x].size() 
#define to v[x][i]
void dfs(int x,int father)
{
	++sz[x]; vis[x]=1;
	for(int i=0;i<Size_;++i)
	{
		if(to==father||vis[to]) continue;
		dfs(to,x);
		fa[to]=x;
		sz[x]+=sz[to],P_in[x]+=P_in[to];
	}
}
int main(int argc, char const *argv[])
{
	n=read();
	for(int i=1;i<n;++i)
	{
		int U=read(),V=read();
		v[U].push_back(V);
		v[V].push_back(U);
	}
	for(int i=1;i<=n;++i)
		Sin+=P_in[i]=read(),Sout+=P_out[i]=read();
	for(int i=1;i<=n;++i)
		P_in[i]/=Sin;
	dfs(1,1);
	for(int x=1;x<=n;++x)
		for(int i=0;i<Size_;++i)
		{
			if(to==fa[x]) res+=(1-P_in[x])*(n-sz[x])*P_out[x];
			else res+=P_in[to]*sz[to]*P_out[x];
		}
	printf("%.12lf",res/Sout);
	return 0;
}