C++(g++ 7.5.0) 解法, 执行用时: 428ms, 内存消耗: 282280K, 提交时间: 2023-01-18 18:57:55

#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ld long double
#define FILE(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)
using namespace std;
const int N=5e5+5,H=71;
double dp[N][H];
int tot=1,fa[N];
inline int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c))
	{
		f=c^'-'?1:-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
inline void change(int p)
{
	double last=dp[p][0];
	dp[p][0]/=2;
	for(int now,h=1;h<H;++h)
	{
		if(!(now=fa[p]))
			break;
		double res=dp[now][h]/(0.5+0.5*last)*(0.5+0.5*dp[p][h-1]);
		p=now;
		last=dp[now][h];
		dp[now][h]=res;
	}
}
inline double query(int x)
{
	double res=0;
	for(int i=1;i<H;++i)
		res+=i*(dp[x][i]-dp[x][i-1]);
	return res;
}
signed main()
{
	int T=read(),q=read();
	fill(dp[1],dp[1]+H,1);
	while(q--)
	{
		int opt=read(),x=read();
		if(opt==1)
		{
			fa[++tot]=x;
			for(int i=0;i<H;++i)
				dp[tot][i]=1;
			change(x);
		}
		else
			printf("%.7lf\n",query(x));
	}
	return 0;
}

C++14(g++5.4) 解法, 执行用时: 508ms, 内存消耗: 162656K, 提交时间: 2019-12-12 14:51:36

#include<bits/stdc++.h>
using namespace std;
const int maxn = 500010;
const int lim = 40;
double dp[maxn][lim];   //i号点dep<=j层的概率
int fa[maxn], sz;

void extend(int x){
    sz++;   fa[sz]=x;
    for (int i=0;i<lim;++i){
        dp[sz][i]=1;
    }
    return ;
}

void update(int x){
    int dep=1, u;
    double pre1, pre2;
    pre1=dp[x][0];
    dp[x][0]*=0.5;
    while(dep<lim && fa[x]!=0){
        u=fa[x];
        pre2=dp[u][dep];
        dp[u][dep]/=(0.5+0.5*pre1);
        dp[u][dep]*=(0.5+0.5*dp[x][dep-1]);
        x=fa[x];    pre1=pre2;
        dep++;
    }
    return ;
}

int main(){
    int T;
    scanf("%*d%d",&T);
    sz=0;
    extend(0);
    int op, x;
    while(T--){
        scanf("%d%d",&op,&x);
        if (op==1){
            extend(x);
            update(fa[sz]);
        }else{
            double ans=0;
            for (int i=1;i<lim;++i){
                ans+=(dp[x][i]-dp[x][i-1])*i;
            }
            printf("%.7f\n",ans);
        }
    }

    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 573ms, 内存消耗: 276304K, 提交时间: 2019-12-09 18:15:24

#include<bits/stdc++.h>
using namespace std;

const int N=500010,sz=70;
int T,q,tot,fa[N];
double f[N][sz];

int main(){
	scanf("%d %d",&T,&q);tot=1;
	fill(f[1]+1,f[1]+sz,1);f[1][0]=0;
	int type,x;
	while(q--){
		scanf("%d %d",&type,&x);
		if(type==1){
			fa[++tot]=x;
			fill(f[tot]+1,f[tot]+sz,1);f[tot][0]=0;
			double now,last=1;
			for(int i=1,op=tot;x!=0 && i<sz;i++,x=fa[op=x]) now=(f[x][i]+1)/2,f[x][i]*=(f[op][i-1]+1)/2/last,last=now;
		}
		else{
			double ans=0;
			for(int i=1;i<sz;i++) ans+=1-f[x][i];
			printf("%.10lf\n",ans);
		}
	}
}