题意
题目链接
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("%.10lfn", ans); } } return 0; }
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/607681.html