1 /*  2 ID:esxgx1  3 LANG:C++  4 PROG:hdu4035  5 */  6 #include <cstdio>  7 #include <cstring>  8 #include <iostream>  9 #include <algorithm> 10 using namespace std; 11  12 template<int maxn, int maxe> 13 class graph { 14     int fw[maxe], t[maxe]; 15     int h[maxn], p; 16  17 public: 18     graph() :p(0) {memset(h, -1, sizeof h);} 19     void clear() {p = 0, memset(h, -1, sizeof h);} 20      21     void addedge(int s, int _t) { 22         fw[p] = h[s], t[p] = _t; 23         h[s] = p++; 24     } 25      26     int begin(int s) {return h[s];} 27     int for_each(int &e, int &_t) { 28         int ret = e; 29         if (~e) { 30             _t = t[e]; 31             e = fw[e];     32         } 33         return ret; 34     }  35      36 }; 37  38 typedef double DB; 39 const int maxn = 10007; 40 graph <maxn, maxn*2> g; 41  42 int adjn[maxn]; 43 int K[maxn], E[maxn]; 44  45 DB A[maxn], B[maxn], C[maxn]; 46  47 #define eps        1e-9 48  49 int dfs(int s, int fa) 50 { 51     DB bfa = (1.0 - (K[s] + E[s])/100.0) / adjn[s]; 52     C[s] = 1.0 - (E[s]+K[s])/100.0, A[s] = K[s]/100.0, B[s] = bfa; 53     DB div = 1.0; 54     for(int e = g.begin(s), t; ~g.for_each(e, t); ) { 55         if (t != fa) { 56             dfs(t, s); 57             A[s] += bfa * A[t], div -= bfa * B[t], 58             C[s] += bfa * C[t]; 59         } 60     } 61     if (div < eps) return 0; 62     A[s] /= div; B[s] /= div; C[s] /= div; 63     return 1; 64 } 65  66 int dfs0(int s, DB &ans) 67 { 68     DB bfa = (1.0 - (K[s] + E[s])/100.0) / adjn[s]; 69     DB div = 1.0; 70     C[s] = 1.0 - (E[s]+K[s])/100.0; 71     for(int e = g.begin(s), t; ~g.for_each(e, t); ) { 72         if (!dfs(t, s)) return 0; 73         div -= bfa * (A[t] + B[t]), 74         C[s] += bfa * C[t]; 75     } 76     if (div < eps) return 0; 77     ans = C[s] / div; 78     return 1; 79 } 80  81 int main(void) 82 { 83     #ifndef ONLINE_JUDGE 84     freopen("in.txt", "r", stdin); 85     #endif 86     int T; 87     scanf("%d", &T); 88     for(int t = 1; t<=T; ++t, g.clear()) { 89         memset(adjn, 0, sizeof adjn); 90         int N; 91         scanf("%d", &N); 92         for(int i=1; i<N; ++i) { 93             int s, t; 94             scanf("%d%d", &s, &t); --s, --t; 95             g.addedge(s, t); 96             g.addedge(t, s); 97             ++adjn[s], ++adjn[t]; 98         } 99         for(int i=0; i<N; ++i)100             scanf("%d%d", &K[i], &E[i]);101         102         double ans;103         if (dfs0(0, ans)) printf("Case %d: %.6f\n", t, ans);104         else printf("Case %d: impossible\n", t);105     }106     return 0;107 }

 1 /* 2 ID:esxgx1 3 LANG:C++ 4 PROG:hdu4035 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <iostream> 9 #include <algorithm>10 using namespace std;11 12 template<int maxn, int maxe>13 class graph {14     int fw[maxe], t[maxe];15     int h[maxn], p;16 17 public:18     graph() :p(0) {memset(h, -1, sizeof h);}19     void clear() {p = 0, memset(h, -1, sizeof h);}20     21     void addedge(int s, int _t) {22         fw[p] = h[s], t[p] = _t;23         h[s] = p++;24     }25     26     int begin(int s) {return h[s];}27     int for_each(int &e, int &_t) {28         int ret = e;29         if (~e) {30             _t = t[e];31             e = fw[e];    32         }33         return ret;34     } 35     36 };37 38 typedef double DB;39 const int maxn = 10007;40 graph <maxn, maxn*2> g;41 42 int adjn[maxn];43 int K[maxn], E[maxn];44 45 DB A[maxn], B[maxn], C[maxn];46 47 #define eps        1e-948 49 int dfs(int s, int fa)50 {51     DB bfa = (1.0 - (K[s] + E[s])/100.0) / adjn[s];52     C[s] = 1.0 - (E[s]+K[s])/100.0, A[s] = K[s]/100.0, B[s] = bfa;53     DB div = 1.0;54     for(int e = g.begin(s), t; ~g.for_each(e, t); ) {55         if (t != fa) {56             dfs(t, s);57             A[s] += bfa * A[t], div -= bfa * B[t],58             C[s] += bfa * C[t];59         }60     }61     if (div < eps) return 0;62     A[s] /= div; B[s] /= div; C[s] /= div;63     return 1;64 }65 66 int main(void)67 {68     #ifndef ONLINE_JUDGE69     freopen("in.txt", "r", stdin);70     #endif71     int T;72     scanf("%d", &T);73     for(int t = 1; t<=T; ++t, g.clear()) {74         memset(adjn, 0, sizeof adjn);75         int N;76         scanf("%d", &N);77         for(int i=1; i<N; ++i) {78             int s, t;79             scanf("%d%d", &s, &t); --s, --t;80             g.addedge(s, t);81             g.addedge(t, s);82             ++adjn[s], ++adjn[t];83         }84         for(int i=0; i<N; ++i)85             scanf("%d%d", &K[i], &E[i]);86 87         if (dfs(0, -1) && 1-A[0] >= eps)88             printf("Case %d: %.6f\n", t, C[0] / (1-A[0]));    89         else printf("Case %d: impossible\n", t);90     }91     return 0;92 }