[problem solving] [show2012] random tree

probability / expect dp Basic questions .

There is a binary tree background .

There are two things worth learning about this problem trick .

First look at the first question . Suppose there is $i-1$ Leaf node , The average depth of each node is $f_{i-1}$ .

Then randomly select a node to copy . The expected depth of this node is $f_{i-1}$

therefore $f_i=\frac{(i-1)f_{i-1}+f_{i-1}+2}{i}=f_{i-1}+\frac{2}{i}$

Let's look at the second question .

set up $g[i][j]$ Express $i$ Second expansion , The depth of the final tree $\ge j$ Of probability .

So the expected depth of the tree ${\sum }_{i=1}^{n-1}g[n-1][i]$

The total number of schemes observed is $(i-1)!$ , If the left subtree $k$ Time , Right subtree $i-k-1$ Time , that $p=\frac{k!(i-k-1)!\left(\genfrac{}{}{0ex}{}{i-1}{k}\right)}{i!}=\frac{1}{i}$ .

So according to probability / The expectation formula ,$$g[i][j]=\frac{{\sum }_{k=0}^{i-1}g[k][j]+g[i-k-1][j]-g[k][j]\ast g[i-k-1][j]}{i}$$

Time complexity $O(n^3)$ .

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=105;
db dp[N],dp2[N][N];
int n,Q;
int main() {
    
	for(int i=1;i<=100;i++) {
    
		dp[i]=dp[i-1]+2.0/(i+1);
	}
	for(int i=0;i<=100;i++) dp2[i][0]=1;
	for(int i=1;i<=100;i++) {
    
		for(int j=1;j<=i;j++) {
    
			for(int k=0;k<i;k++) {
    
				dp2[i][j]+=(dp2[k][j-1]+dp2[i-k-1][j-1]-dp2[k][j-1]*dp2[i-k-1][j-1])/i;
			}
		}
	}
	scanf("%d%d",&Q,&n);
	if(Q==1) printf("%lf",dp[n-1]);
	else {
    
		db res=0;
		for(int i=1;i<=n-1;i++) {
    
			res+=dp2[n-1][i];
		}
		printf("%lf",res);
	}
}