청두 지역 경기 지역 마즈항전 4035(dp 기대)

문제풀이 사고 분석 과정 전재:
02. dp가 원하는 문제를 구한다.03. 제목: 04.n개의 방이 있는데 n-1개의 터널이 연결되어 실제로는 나무 한 그루가 형성되었다.결점 1에서 출발하여 걷기 시작하면 매 결점 i마다 3가지 가능성이 있다. 06.        1.살해, 결점 1곳으로 돌아가기(확률 키)07.        2.출구를 찾아 미로를 벗어나다(확률은 ei)08.        3.이 점과 m변이 연결되어 있어 무작위로 09.구: 미궁에서 벗어나 가려는 변수의 기대치.10.      11.E[i]를 설정하면 결점 i에서 미궁에서 벗어나려는 변수의 기대를 나타낸다.E[1]이 필요합니다.12.      13.잎 결점:14.    E[i] = ki*E[1] + ei*0 + (1-ki-ei)*(E[father[i]] + 1); 15.         = ki*E[1] + (1-ki-ei)*E[father[i]] + (1-ki-ei); 16.      17.비엽자 결점: (m는 결점과 연결된 변수) 18.    E[i] = ki*E[1] + ei*0 + (1-ki-ei)/m*( E[father[i]]+1 + ∑( E[child[i]]+1 ) ); 19.         = ki*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei)/m*∑(E[child[i]]) + (1-ki-ei); 20.      21.각 결점을 설정: E[i] = Ai*E[1] + Bi*E[father[i]] + Ci;22.      23.비엽자 결점 i에 대해 j를 i로 하는 아이 결점은 24.    ∑(E[child[i]]) = ∑E[j] 25.                   = ∑(Aj*E[1] + Bj*E[father[j]] + Cj) 26.                   = ∑(Aj*E[1] + Bj*E[i] + Cj) 27.덧붙이다    (1 - (1-ki-ei)/m*∑Bj)*E[i] = (ki+(1-ki-ei)/m*∑Aj)*E[1] + (1-ki-ei)/m*E[father[i]] + (1-ki-ei) + (1-ki-ei)/m*∑Cj; 29.여기서 30을 얻을 수 있다.    Ai =        (ki+(1-ki-ei)/m*∑Aj)  /(1 - (1-ki-ei)/m*∑Bj); 31.    Bi =        (1-ki-ei)/m           /(1 - (1-ki-ei)/m*∑Bj); 32.    Ci = ( (1-ki-ei)+(1-ki-ei)/m*∑Cj )/(1 - (1-ki-ei)/m*∑Bj); 33.      34.잎 결점    Ai = ki; 36.    Bi = 1 - ki - ei; 37.    Ci = 1 - ki - ei; 38.      39.잎사귀 결점부터 A1, B1, C1까지 계산하기;40.      41.    E[1] = A1*E[1] + B1*0 + C1; 그래서    E[1] = C1/(1 - A1); 44. A1이 1에 가까워지면 해가 없다...45.**/   

#include <cstdio>   
#include <iostream>   
#include <vector>   
#include <cmath>   
 
using namespace std;  
 
const int MAXN = 10000 + 5;  
 
double e[MAXN], k[MAXN];  
double A[MAXN], B[MAXN], C[MAXN];  
 
vector<int> v[MAXN];  
 
bool search(int i, int fa)  
{  
    if ( v[i].size() == 1 && fa != -1 )  
    {  
        A[i] = k[i];  
        B[i] = 1 - k[i] - e[i];  
        C[i] = 1 - k[i] - e[i];  
        return true;  
    }  
 
    A[i] = k[i];  
    B[i] = (1 - k[i] - e[i]) / v[i].size();  
    C[i] = 1 - k[i] - e[i];  
    double tmp = 0;  
      
    for (int j = 0; j < (int)v[i].size(); j++)  
    {  
        if ( v[i][j] == fa ) continue;  
        if ( !search(v[i][j], i) ) return false;  
        A[i] += A[v[i][j]] * B[i];  
        C[i] += C[v[i][j]] * B[i];  
        tmp  += B[v[i][j]] * B[i];  
    }  
    if ( fabs(tmp - 1) < 1e-10 ) return false;  
    A[i] /= 1 - tmp;  
    B[i] /= 1 - tmp;  
    C[i] /= 1 - tmp;  
    return true;  
}  
 
int main()  
{  
    int nc, n, s, t;  
  int i;
    cin >> nc;  
    for (int ca = 1; ca <= nc; ca++)  
    {  
        cin >> n;  
        for (i = 1; i <= n; i++)  
            v[i].clear();  
 
        for ( i = 1; i < n; i++)  
        {  
            cin >> s >> t;  
            v[s].push_back(t);  
            v[t].push_back(s);  
        }  
        for ( i = 1; i <= n; i++)  
        {  
            cin >> k[i] >> e[i];  
            k[i] /= 100.0;  
            e[i] /= 100.0;  
       }  
         
       cout << "Case " << ca << ": ";  
       if ( search(1, -1) && fabs(1 - A[1]) > 1e-10 )  
           cout << C[1]/(1 - A[1]) << endl;  
       else  
            cout << "impossible" << endl;  
    }  
    return 0;  
}