传送门
Solution
我们考虑一下设(f(x))表示当(n)为(x)时构造二叉树的方案数,(g(x))表示当(n)为(x)时构造二叉树的叶子节点数的总和.
仔细看一下这个句子:当$n$为$x$时构造二叉树的方案数.(Catalan)数无疑了,接着就是解决(g(x))是什么.
现在不是有(g(x))个叶子对吧,那么我们把这些叶子分别删掉,那么就是(g(x))个(n-1)的节点的树.
然后算上贡献就是(f(x-1)*x)对吧.
接着你可以写出一个式子:
[Ans=frac{(2n-2)!n!(n+1)!}{(2n)!(n-1)!n!}
\
=frac{n(n+1)}{2*(2n-1)}
]
代码实现
/*
mail: mleautomaton@foxmail.com
author: MLEAutoMaton
This Code is made by MLEAutoMaton
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define ll long long
#define re register
#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
inline ll gl()
{
ll f=1,sum=0;char ch=getchar();
while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return f*sum;
}
ll n;
int main()
{
n=gl();
printf("%.9lf
",n*(n+1)*1./((2*n-1)*2));
return 0;
}