Description:
给你一棵初始只有根为1的树
两种操作
1 x 表示加入一个新点以 x为父亲
2 x 表示以 x 为根的子树期望最深深度
每条边都有 \(\frac{1}{2}\) 的概率断裂。
Solution:
\[ E(\max\{A\}) \not=\max\{E(A)\} \]
所以一般会从定义出发，设 \(dp[x][i]\) 表示以 \(x\) 为根，深度为 \(i\) 的概率。
然后不好确定这个深度是在哪取到，所以可以设 \(dp[x][i]\) 为深度 \(\le i\) 的概率，不难发现这样每个子树就是独立的了。\[ dp[x][i] = \prod_{v\in son(x)}\frac{dp[x][i - 1] + 1}{2} \] 加1是因为 \((x, v)\) 这条边可能会断，那么如果断了，那么 \(dep\le i - 1\) 的概率一定是1。
深度较大时期望值很小(它的缩减率是指数级的), 因为允许精度误差所以可以忽略. 加入每个点时把上面 50 个祖先的 \(dp\) 值更新一下即可。
Summary:
在难以刻画细小的状态时可以将状态设广范些，但要保证前后可以互相转换。
Code:
#include <vector>
#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long LL;
typedef unsigned long long uLL;
#define fir first
#define sec second
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define MP(x, y) std::make_pair(x, y)
#define PB(x) push_back(x)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define GO cerr << "GO" << endl;
#define DE(x) cerr << x << endl;
#define rep(i, a, b) for (register int i = (a), i##_end_ = (b); (i) <= i##_end_; ++ (i))
#define drep(i, a, b) for (register int i = (a), i##_end_ = (b); (i) >= i##_end_; -- (i))
#define REP(i, a, b) for (register int i = (a), i##_end_ = (b); (i) < i##_end_; ++ (i))
inline int read() {
register int x = 0; register int f = 1; register char c;
while (!isdigit(c = getchar())) if (c == '-') f = -1;
while (x = (x << 1) + (x << 3) + (c xor 48), isdigit(c = getchar()));
return x * f;
}
template<class T> inline void write(T x) {
static char stk[30]; static int top = 0;
if (x < 0) { x = -x, putchar('-'); }
while (stk[++top] = x % 10 xor 48, x /= 10, x);
while (putchar(stk[top--]), top);
}
template<typename T> inline bool chkmin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
using namespace std;
const int maxN = 5e5 + 1;
const int D = 50;
int Q, fa[maxN], ncnt;
double dp[maxN][D];
void clear(int x, int son, int cnt)
{
if (!x || cnt >= D) return;
clear(fa[x], x, cnt + 1);
for (int i = 1; i < D; ++i)
dp[x][i] /= 0.5 * (dp[son][i - 1] + 1);
}
void update(int x, int son, int cnt)
{
if (!x || cnt >= D) return;
for (int i = 1; i < D; ++i)
dp[x][i] *= 0.5 * (dp[son][i - 1] + 1);
update(fa[x], x, cnt + 1);
}
double ask(int x)
{
double ans(0);
for (int i = 1; i < D; ++i)
ans += (double) i * (dp[x][i] - dp[x][i - 1]);
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("xhc.in", "r", stdin);
freopen("xhc.out", "w", stdout);
#endif
Q = read();
ncnt = 1;
fa[1] = 0;
fill(dp[1], dp[1] + D, 1);
while (Q--)
{
int op = read(), x = read();
if (op == 1)
{
fa[++ncnt] = x;
clear(fa[x], x, 1);
fill(dp[ncnt], dp[ncnt] + D, 1);
dp[x][0] *= 0.5;
update(x, ncnt, 0);
} else
{
printf("%.7lf\n", ask(x));
}
}
return 0;
}
转载于:https://www.cnblogs.com/cnyali-Tea/p/11439907.html
相关资源：JAVA上百实例源码以及开源项目
