cf643E. Bear and Destroying Subtrees(期望dp)

题意

题目链接

 

sol

这种dp是第一次见啊，interesting。

设$f[i][j]$表示第$i$个节点，深度$\leqslant j$的概率

转移的时候分两种情况讨论

$f[i][j] = \prod \frac{1}{2}f[son[i]][j-1] + \frac{1}{2}$

由于修改操作只会影响到一条链的dp值，因此暴力往上update即可

考虑到dp值与深度有关，当深度$h>70$时$\frac{1}{2^{70}} < 10^{-6}$

因此只dp 70层即可

#include<cstdio>
#include<algorithm>
#include<vector>
//#define int long long 
using namespace std;
const int maxn = 5 * 1e5 + 10, maxh = 60;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int t, q, fa[maxn], n;
vector<int> v[maxn];
double f[maxn][61];
void mem(double *f) {
    for(int i = 0; i <= maxh; i++) f[i] = 1;
}
main() {
    q = read(); n = 1;
    mem(f[1]);
    while(q--) {
        int opt = read(), x = read();
        if(opt == 1) {
            fa[++n] = x; 
            mem(f[n]);
            double pre = f[x][0], now;
            f[x][0] *= 0.5;
            for(int h = 1; h <= maxh; h++, x = fa[x]) {
                now = f[fa[x]][h];
                f[fa[x]][h] /= 0.5 + 0.5 * pre;
                f[fa[x]][h] *= 0.5 + 0.5 * f[x][h - 1];
                pre = now;
            }
        } else if(opt == 2) {
            double ans = 0;
            for(int i = 0; i <= maxh; i++) ans += i * (f[x][i] - f[x][i - 1]);
            printf("%.10lf\n", ans);
        }
    }
    return 0;
}