HDU4035（概率期望、树形、数学）

和ZOJ3329有些像，都是用期望列出来式子以后，为了解式子，设A[i],B[i]，此题又多了C[i]，然后用递推（此题是树形dp）去求得ABC，最后结果只跟ABC有关，跟列写的期望数组根本无关。

虽然式子很长很冗，但平心而论思维上并不难理解，关键是自信和耐心去带入。ABC的递推式出来了以后，代码就不难了。

据说eps有坑？

邝斌巨巨的：

  1 #pragma comment(linker, "/STACK:1024000000,1024000000")
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <ctime>
  7 #include <cctype>
  8 #include <climits>
  9 #include <iostream>
 10 #include <iomanip>
 11 #include <algorithm>
 12 #include <string>
 13 #include <sstream>
 14 #include <stack>
 15 #include <queue>
 16 #include <set>
 17 #include <map>
 18 #include <vector>
 19 #include <list>
 20 #include <fstream>
 21 #include <bitset>
 22 #define init(a, b) memset(a, b, sizeof(a))
 23 #define rep(i, a, b) for (int i = a; i <= b; i++)
 24 #define irep(i, a, b) for (int i = a; i >= b; i--)
 25 using namespace std;
 26 
 27 typedef double db;
 28 typedef long long ll;
 29 typedef unsigned long long ull;
 30 typedef pair<int, int> P;
 31 const int inf = 0x3f3f3f3f;
 32 const ll INF = 1e18;
 33 
 34 template <typename T> void read(T &x) {
 35     x = 0;
 36     int s = 1, c = getchar();
 37     for (; !isdigit(c); c = getchar())
 38         if (c == '-')    s = -1;
 39     for (; isdigit(c); c = getchar())
 40         x = x * 10 + c - 48;
 41     x *= s;
 42 }
 43 
 44 template <typename T> void write(T x) {
 45     if (x < 0)    x = -x, putchar('-');
 46     if (x > 9)    write(x / 10);
 47     putchar(x % 10 + '0');
 48 }
 49 
 50 template <typename T> void writeln(T x) {
 51     write(x);
 52     puts("");
 53 }
 54 
 55 const int maxn = 1e4 + 5;
 56 const db eps = 1e-9;
 57 int T, n, kase;
 58 db A[maxn], B[maxn], C[maxn], K[maxn], E[maxn];
 59 vector<int> v[maxn];
 60 
 61 bool dfs(int cur, int fa) {
 62     int m = v[cur].size();
 63     if (m == 1 && fa) {
 64         A[cur] = K[cur];
 65         B[cur] = C[cur] = 1.0 - K[cur] - E[cur];
 66     } else {
 67         db tmp = (1 - K[cur] - E[cur]) / m;
 68         db Atmp = 0, Btmp = 0, Ctmp = 0;
 69         for (int child : v[cur]) {
 70             if (child != fa) {
 71                 if (!dfs(child, cur))    return false;
 72                 Atmp += A[child];
 73                 Btmp += B[child];
 74                 Ctmp += C[child];
 75             }
 76         }
 77         if (fabs(1 - tmp * Btmp) < eps)    return false;
 78         A[cur] = (K[cur] + tmp * Atmp) / (1 - tmp * Btmp);
 79         B[cur] = tmp / (1 - tmp * Btmp);
 80         C[cur] = (tmp * Ctmp + 1 - K[cur] - E[cur]) / (1 - tmp * Btmp);
 81     }
 82     return true;
 83 }
 84 
 85 int main() {
 86     for (read(T); T; T--) {
 87         read(n);
 88         rep(i, 1, n)    v[i].clear();
 89         rep(i, 1, n - 1) {
 90             int x, y;
 91             read(x), read(y);
 92             v[x].push_back(y);
 93             v[y].push_back(x);
 94         }
 95         rep(i, 1, n) {
 96             read(K[i]), read(E[i]);
 97             K[i] /= 100, E[i] /= 100;
 98         }
 99 
100         printf("Case %d: ", ++kase);
101         if (dfs(1, 0) && fabs(1 - A[1]) > eps) {
102             printf("%.6lf
", C[1] / (1 - A[1]));
103         } else {
104             puts("impossible");
105         }
106     }
107     return 0;
108 }