题目大意
有一个树形的迷宫，从节点1开始走，每个节点都有(k_i)的概率回到1，(e_i)的概率逃出迷宫，每个房间有(m)条边相连，求走出迷宫所需步数的期望。
解题思路
设走出迷宫步数的期望为(E_i)，父亲为(F_i)，儿子为(S_i)，相邻的节点个数为(m)，则(E_1)即为所求。
对于叶子节点来说，可以得到: (E_i = k_i imes E_1 + (1-k_i-e_i) imes (1 + E_{F_i}))。
即(E_i = k_i imes E_1 + (1-k_i-e_i) imes E_{F_i} + 1-k_i-e_i)。
对于非叶子节点来说，可以得到: (E_i = k_i imes E_1 + frac{(1-k_i-e_i)}{m} imes (1 + E_{F_i} + sum (E_{S_i} + 1)))。
即(E_i = k_i imes E_1 + frac{(1-k_i-e_i)}{m} imes E_{F_i} + frac{(1-k_i-e_i)}{m} imes sum E_{S_i} + 1-k_i-e_i)。
我们发现每个式子中都有(E_1)这个变量，这是不便于我们递推的，我们可以尝试把递推的值转为一次函数。
设(E_i = A_i imes E_1 + B_i imes E_{F_i} + C_i), 那么将这个式带入非叶节点的公式替换掉(E_{S_i})可得:
(E_i = k_i imes E_1 + frac{(1-k_i-e_i)}{m} imes E_{F_i} + frac{(1-k_i-e_i)}{m} imes (sum (A_{S_i} imes E_1 + B_{S_i} imes E_i + C_{S_i})) + 1-k_i-e_i)
整理得: ((1 - frac{(1-k_i-e_i)}{m} imes sum B_{S_i}) imes E_i = (k_i + frac{(1-k_i-e_i)}{m} imes sum A_{S_i}) imes E_1 + frac{(1-k_i-e_i)}{m} imes E_{F_i} + 1-k_i-e_i + frac{(1-k_i-e_i)}{m} imes sum C_{S_i})
(A_i = (k_i + frac{1-k_i-e_i}{m} imes sum A_{S_i}) / (1 - frac{1-k_i-e_i}{m} imes sum B_{S_i}))
(B_i = (frac {1-k_i-e_i}{m}) / (1 - frac{1-k_i-e_i}{m} imes sum B_{S_i}))
(C_i = (1-k_i-e_i + frac {1-k_i-e_i}{m} imes sum C_{S_i}) / (1 - frac{1-k_i-e_i}{m} imes sum B_{S_i}))
这样我们通过递推出(A_1, B_1, C_1)就能得到答案了。
代码
const int maxn = 1e5+10;
const int maxm = 2e6+10;
double k[maxn], e[maxn];
vector<int> g[maxn];
int n;
double a[maxn], b[maxn], c[maxn];
void init() {
clr(a, 0); clr(b, 0); clr(c, 0);
for (int i = 0; i<=n; ++i) g[i].clear();
}
bool dfs(int u, int p) {
double m = g[u].size();
double pi = (1-k[u]-e[u])/m;
double sum1 = k[u], sum2 = pi, sum3 = 1-k[u]-e[u], sum = 0;
for (auto v : g[u]) {
if (v==p) continue;
if (!dfs(v, u)) return 0;
sum1 += pi*a[v];
sum += pi*b[v];
sum3 += pi*c[v];
}
sum = 1-sum;
if (fabs(sum)<eps) return 0;
a[u] = sum1/sum;
b[u] = sum2/sum;
c[u] = sum3/sum;
return 1;
}
int main(void) {
//IOS;
int __; cin >> __;
int kase = 0;
while(__--) {
cin >> n;
init();
for (int i = 1; i<n; ++i) {
int a, b; scanf("%d%d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = 1; i<=n; ++i) {
scanf("%lf", &k[i]); k[i] /= 100.0;
scanf("%lf", &e[i]); e[i] /= 100.0;
}
if (dfs(1, -1) && fabs(1-a[1])>eps) printf("Case %d: %.6f
", ++kase, c[1]/(1-a[1]));
else printf("Case %d: impossible
", ++kase);
}
return 0;
}