翻译
给你一棵初始只有根为1的树
两种操作
1 x表示加入一个新点以x为父亲
2 x表示以x为根的子树期望最深深度
每条边都有 1 2 \frac{1}{2} 21?的概率断裂
题解
性质：我们只用考虑40层以内的节点 因为深度过大的的概率太小不予考虑
设 f [ i ] [ j ] f[i][j] f[i][j]表示以i为根的子树 最深深度不大于j的概率
计算答案可以直接
∑ ( f [ x ] [ i ] ? f [ x ] [ i ? 1 ] ) ? i \sum(f[x][i]-f[x][i-1])*i ∑(f[x][i]?f[x][i?1])?i
考虑一个点加入的影响
首先期望深度为0的话肯定是 1 2 \frac{1}{2} 21?的儿子个数次方
一层层往上更新
第一个祖先 只会影响到他的f[x][1]
第二个祖先 只会影响到他的f[x][2]，大于2的我们达不到，小于2的断了我们这条边还存在影响
…
直接更新即可
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<vector> #include<ctime> #include<map> #define LL long long #define mp(x,y) make_pair(x,y) using namespace std; inline int read() {
int f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';ch=getchar();}return x*f; } inline void write(int x) {
if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0'); } inline void print(int x){
write(x);printf(" ");} double f[510000][45]; int fa[510000],son[510000]; double pow_mod(double a,int b) {
double ret=1;while(b){
if(b&1)ret=ret*a;a=a*a;b>>=1;}return ret; } int main() {
int o=1;for(int i=0;i<=40;i++)f[1][i]=1;int T=read();while(T--){
int op=read(),x=read();if(op==1){
o++;fa[o]=x;son[x]++;double lst=f[x][0];f[x][0]=pow_mod(0.5,son[x]);for(int i=0;i<=40;i++)f[o][i]=1;for(int i=1;i<=40;i++){
int u=fa[x];if(!u)break;double gg=f[u][i];f[u][i]/=(0.5+0.5*lst);f[u][i]*=(0.5+0.5*f[x][i-1]);lst=gg;x=u;}}else{
double ans=0.0;for(int i=1;i<=40;i++)ans+=(f[x][i]-f[x][i-1])*(double)i;printf("%.10lf\n",ans);}}return 0; }