失踪人口回归
题意：给你一棵$n$个点的树，从$1$开始走，在第$i$个点有$k_i$的概率跳回$1$（不算经过边），有$e_i$的概率结束游走，问期望步数。
题解：设$f[x]$表示从$x$开始走的期望步数。
然后我就不会了，只能想到高斯消元，然而n ≤ 10000根本跑不过去。。于是膜了题解
考虑树形DP中dfs的过程，我们是先求出儿子的答案再求出当前点的答案的，所以$f[y]$可以当成常量。所以设
把这个式子代入前面的式子得到
写公式好累啊QAQ
相信聪明的你已经看出来$A, B, C$怎么推了吧。
答案就是$f[1] = \frac{C_1}{1 - A_1}$，如果$A1 = 1$那就无解。
代码：
#include <bits/stdc++.h>
using namespace std;
int T, n, num = 0, fst[10010], deg[100010];
struct edge
{
int x, y, n;
} e[20010];
double a[10010], b[10010], c[10010], k[10010], E[10010];
const double eps = 1e-10;
void ins(int x, int y)
{
e[++num] = {x, y, fst[x]};
fst[x] = num;
}
void dfs(int x, int fa)
{
if (deg[x] == 1 && fa)
{
a[x] = k[x];
c[x] = b[x] = 1 - k[x] - E[x];
return;
}
double sa = 0, sb = 0, sc = 0;
for (int i = fst[x]; i; i = e[i].n)
{
int y = e[i].y;
if (y == fa) continue;
dfs(y, x);
sa += a[y];
sb += b[y];
sc += c[y];
}
double hh = (1 - k[x] - E[x]) / deg[x], oo = 1 - hh * sb;
a[x] = (hh * sa + k[x]) / oo;
b[x] = hh / oo;
c[x] = (hh * sc + 1 - k[x] - E[x]) / oo;
}
int main()
{
scanf("%d", &T);
int cs = 0;
while (T--)
{
scanf("%d", &n);
memset(fst, 0, sizeof(fst));
memset(deg, 0, sizeof(deg));
num = 0;
for (int i = 1; i < n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
ins(x, y);
ins(y, x);
deg[x]++;
deg[y]++;
}
for (int i = 1; i <= n; i++)
{
scanf("%lf%lf", &k[i], &E[i]);
k[i] /= 100;
E[i] /= 100;
}
dfs(1, 0); /*
for (int i = 1; i <= n; i++)
printf("%lf %lf %lf\n", a[i], b[i], c[i]);*/
printf("Case %d: ", ++cs);
if (abs(a[1] - 1) < eps)
puts("impossible");
else
printf("%lf\n", c[1] / (1 - a[1]));
}
}