这种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;
}