先上题目

Maze

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65768/65768 K (Java/Others) Total Submission(s): 367    Accepted Submission(s): 103 **Special Judge**

Problem Description**

When wake up, lxhgww find himself in a huge maze.

The maze consisted by N rooms and tunnels connecting these rooms. Each pair of rooms is connected by one and only one path. Initially, lxhgww is in room 1. Each room has a dangerous trap. When lxhgww step into a room, he has a possibility to be killed and restart from room 1. Every room also has a hidden exit. Each time lxhgww comes to a room, he has chance to find the exit and escape from this maze.

Unfortunately, lxhgww has no idea about the structure of the whole maze. Therefore, he just chooses a tunnel randomly each time. When he is in a room, he has the same possibility to choose any tunnel connecting that room (including the tunnel he used to come to that room). What is the expect number of tunnels he go through before he find the exit?

Input**

First line is an integer T (T ≤ 30), the number of test cases.

At the beginning of each case is an integer N (2 ≤ N ≤ 10000), indicates the number of rooms in this case.

Then N-1 pairs of integers X, Y (1 ≤ X, Y ≤ N, X ≠ Y) are given, indicate there is a tunnel between room X and room Y.

Finally, N pairs of integers Ki and Ei (0 ≤ Ki, Ei ≤ 100, Ki + Ei ≤ 100, K1 = E1 = 0) are given, indicate the percent of the possibility of been killed and exit in the ith room.

Output**

For each test case, output one line “Case k: ”. k is the case id, then the expect number of tunnels lxhgww go through before he exit. The answer with relative error less than 0.0001 will get accepted. If it is not possible to escape from the maze, output “impossible”.

Sample Input**

3

3

1 2

1 3

0 0

100 0

0 100

3

1 2

2 3

0 0

100 0

0 100

6

1 2

2 3

1 4

4 5

4 6

0 0

20 30

40 30

50 50

70 10

20 60

Sample Output**

Case 1: 2.000000

Case 2: impossible

Case 3: 2.895522

Source**

The 36th ACM/ICPC Asia Regional Chengdu Site —— Online Contest

先说说题意，题意是有一个树形的迷宫，主角没有记忆，只会瞎走，然后对于除起点外的每一个点，主角有Ei的概率发现出口而走出去，有Ki的概率掉进陷阱回到起点，剩下(1-Ei-Ki)的概率会随机选择一条通道往下走（包括走到这个点的通道，也就是说回到父亲节点），求走出迷宫所需要经过通道数的期望

看到题目很容易想到是一道树形DP，但是真的要做会发现无从着手，感觉没有一个很好的办法得到一个求期望的递推式- -据说可以用二分的办法，不过我用的是利用解方程的办法，设ans[i]为从i个点出发所需要的步数的期望，再设三个未知数,A[i],B[i],C[i]，令ans[i]=A[i]+B[i]ans[1]+C[i]ans[fa[i]],其中fa[i]为i的父亲节点，而根据已知条件，有

ans[i]=Kians[1]+(sigma(1+ans[son[i]])+(1+ans[fa[i]]))(1-Ei-Ki)/m，其中m是连接到这个点的通道数,sigma(1+ans[son[i]]))是i所有儿子的期望加1之后再求和

展开，并把ans[son[i]]=A[son[i]]+B[son[i]]ans[1]+C[son[i]]ans[fa[son[i]]],其中ans[fa[son[i]]]自然就是ans[i]

化简一下，可以得到ans[i]=(1-Ei-Ki)+(Ki+sigma(B[son[i]])(1-Ei-Ki)/m)+((1-Ei-Ki)/m)+(sigma(C[son[i]])((1-Ei-Ki)/m)*ans[i])

跟ans[i]=A[i]+B[i]ans[1]+C[i]ans[fa[i]]对号入座一下，发现多出来一个(sigma(C[son[i]])((1-Ei-Ki)/m)ans[i]),移到等式左边，再把系数除到右边，就得到ans[i]=((1-Ei-Ki)+(Ki+sigma(B[son[i]])(1-Ei-Ki)/m)+((1-Ei-Ki)/m))/(1-sigma(C[son[i]])((1-Ei-Ki)/m))

嗯- -很漂亮的一个递推式就出来了

这个式子基本上是通用的，对于叶子节点，不存在son而且m=1，对于普通节点没有什么好说的，对于根节点是不存在父节点的，也就是说C[1]是没有意义的。

用这个递推式推到ans[1]之后，可以得到ans[1]=A[1]+B[1]ans[1]+C[1]ans[fa[1]],C[1]不用去管他，直接得到ans[1]=A[1]/(1-B[1])

而当B[1]=1（实际编程的时候要考虑误差，取B[1] >= 1-1e-15)的时候，就是无解的时候，输出impossible

贴上代码吧- -我的代码里面一开始是把普通节点跟叶子节点分开考虑的，后来发现没有必要，所以把分考考虑那部分代码注释掉了，但是没删掉

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

int nCase, kCase;

vector<int> a[10010];
int K[10010], E[10010];
double A[10010], B[10010], C[10010];
//int flag[10010];

void dfs(int fa, int i)
{
//	if(flag[i])
//		return;
//	flag[i] = 1;
//	if(a[i].size() == 1 && fa != 0){
//		A[i] = (100-E[i]-K[i])/100.0;
//		B[i] = K[i]/100.0;
//		C[i] = (100-E[i]-K[i])/100.0;
//	}else if(a[i].size()>1 || fa == 0){
		int m = a[i].size();
		A[i] = (100-E[i]-K[i])/100.0;
		B[i] = K[i]/100.0;
		double tmp = (100-E[i]-K[i])/100.0/m;
		C[i] = tmp;
		double tt = 0;
		for(vector<int>::iterator index = a[i].begin(); index!=a[i].end(); ++index){
			if(*index != fa){
				dfs(i, *index);
				A[i] += A[*index]*tmp;
				B[i] += B[*index]*tmp;
				tt += C[*index]*tmp;
			}
		}
		A[i] /= (1-tt);
		B[i] /= (1-tt);
		C[i] /= (1-tt);
//	}
//	flag[1] = 0;
}

void Solve()
{
	int n;
	scanf("%d", &n);
	for(int i = 0; i<=n; ++i)
		a[i].clear();
	for(int i = 0; i<n-1; ++i){
		int u, v;
		scanf("%d%d", &u, &v);
		a[u].push_back(v);
		a[v].push_back(u);
	}
	for(int i = 1; i<=n; ++i){
		scanf("%d%d", &K[i], &E[i]);
	}
//	memset(flag, 0, sizeof(flag));
	dfs(0, 1);
	if(B[1] >= (1-1e-15))
		printf("Case %d: impossible\n", kCase);
	else
		printf("Case %d: %.6f\n", kCase, A[1]/(1-B[1]));
//	for(int i = 1; i<=n; ++i){
//		printf("%7.4f%7.4f%7.4f\n", A[i], B[i], C[i]);
//	}
}

int main(int argc, char** argv)
{
	double f = 1e-20;
	printf("%d\n", 1-f == 1);
	return 0;
	scanf("%d", &nCase);
	for(kCase = 1; kCase <= nCase; ++kCase){
		Solve();
	}
	return 0;
}