学步园

题意： 
    有n个房间，由n-1条隧道连通起来，实际上就形成了一棵树，
    从结点1出发，开始走，在每个结点i都有3种可能：
        1.被杀死，回到结点1处（概率为ki）
        2.找到出口，走出迷宫 （概率为ei）
        3.和该点相连有m条边，随机走一条
    求：走出迷宫所要走的边数的期望值。




做法：
    dp[i]表示从房间i开始逃出去的期望。那么题目要求的答案就是dp[1]。
    
    定义dp的含义以后，我们很容易推出转移方程：
   （注：SUM（）为对其所有相邻点v的情况和）


     dp[i] = ki*dp[1] + ei*0+ SUM( ( 1-ki-ei)/m*(dp[v]+1) );  
     (i != 1, v为所有相邻点, m[i]为相邻点的个数)

     对于这题，我们要把所有相邻点分为  父亲 和 儿子 两类， 之后会发现这种分法是有理由的
     
     对于叶子节点：
     dp[i] = ki*dp[1] + (1-ki-ei)*dp[fa[i]] + (1-ki-ei);


     对于非叶子节点：
     dp[i] = ki*dp[1] + SUM( ( 1-ki-ei)/m[i]*dp[v] )+(1-ki-ei) ) *dp[fa[i]] 
     + ( 1-ki-ei); 
 
     我们就可以得到n个方程组，解出这个方程组就可以算出答案dp[1]了。


     方程组求解：迭代法

     我们从叶子节点出发，不断把叶子节点的方程代到其父亲节点上去，这样就能解出dp[1]了。


     我们以u--->v为例， u为父亲， v为所有u的儿子

     为了方便推导，我们设 A[i] = ki，  B[i] = (1-ki-ei)/m[i]， C[i] = 1-ki-ei
     (即叶子节点的每项系数)


     把叶子节点代入其父亲节点， 化简整理得：


     dp[u] ={ 
            ( A[u]+B[u]*SUM(A[v]) )*dp[1] + B[u]*dp[fa[u]] 
            + C[u] +  SUM(C[v])*B[u]
	    } / (1 - B[u]* SUM(B[v]) );
    然后更新u节点的方程系数(A[u], B[u], C[u]) 不断往上代入。


    最后得dp[1] = A[1]*dp[1] + C[1]; （1没有父亲）。
    解出dp[1]即可， 注意在往上代入方程的时候会用到除法， 当分母为零时方程无解，即为impossible


代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#define pb push_back
using namespace std;
const int maxn = 10003;
const double eps = 1e-9;
int n, x, y;
double k[maxn], e[maxn];
double A[maxn], B[maxn], C[maxn];
int len[maxn];
struct Edge {
	int v, next;
}edge[maxn<<1];

int head[maxn], E;
inline void init() {
	E = 0;
	memset(head, -1, sizeof(int)*(n+1));
}
inline void add(int s, int t) {
	edge[E].v = t;
	edge[E].next = head[s];
	head[s] = E++;
	edge[E].v = s;
	edge[E].next = head[t];
	head[t] = E++;
}
inline bool dfs(int u, int fa) {
	int i;
	A[u] = k[u];
	B[u] = (1-k[u]-e[u])/len[u];
	C[u] = (1-k[u]-e[u]);
	double tmp = 0;
	for(i = head[u]; ~i; i = edge[i].next) {
		int v = edge[i].v;
		if(v == fa) continue;
		if(!dfs(v, u)) return 0;
		A[u] += B[u]*A[v];
		C[u] += B[u]*C[v];
		tmp += B[u]*B[v];
	}
	tmp = 1-tmp;
	if(tmp < eps) return 0;
	A[u] /= tmp;
	B[u] /= tmp;
	C[u] /= tmp;
	return 1;
}
int main() {
	int i, cas;
	scanf("%d", &cas);
	for(int ca = 1; ca <= cas; ca++) {
		scanf("%d", &n);
		init();
		memset(len, 0, sizeof(int)*(n+1));
		for(i = 1; i < n; i++) {
			scanf("%d%d", &x, &y);
			add(x, y);
			len[x]++; len[y]++;
		}
		for(i = 1; i <= n; i++) {
			scanf("%lf%lf", &k[i], &e[i]);
			k[i] /= 100;
			e[i] /= 100;
		}
		printf("Case %d: ", ca);
		if(dfs(1, -1) && (1-A[1]) > eps) {
			printf("%.6f\n", C[1]/(1-A[1]));
		}
		else puts("impossible");
	}
	return 0;
}