感谢@JCarlson 的翻译

(其实也要感谢@似水流年 帮忙了虽然..她没看懂..)

题意:

给你一棵二叉树

求1~n这n个权值分给这个二叉树并且使得这个二叉树满足小根堆的方案数有多少

n<=200

我们考虑每个分叉

首先假设这个子树的大小是x

我们显然把最小的给根,然后左右任意分互不影响

所以左边就是C(x-1,size[left])种,右边是剩下的

乘一下就好了

一看就知道要写高精度..

这题我高精度开的有点过了..竟然MLE了一次..

以后要学会算空间问题....

可以说..这次以后学会了正确的写一些东西的姿势..

比如..

(inline) int & operator [](int x)

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
struct bigint
{
    int a[105];
    bigint (int x=0)
    {
        memset(a,0,sizeof(a));
        a[0]=x;
    }
    int & operator [](int x)
    {
        return a[x];
    }
    friend bigint operator + (const bigint &a,bigint &b)
    {
        int i;
        bigint c=a;
        for (i=0;i<100;i++)
        {
            c[i]+=b[i];
            if (c[i]>=10000)
            {
                c[i+1]++;
                c[i]-=10000;
            }
        }
        return c;
    }
    friend bigint operator * (bigint &a,bigint &b)
    {
        bigint c;
        int i;
        for (i=0;i<100;i++)
        {
            int j;
            for (j=0;i+j<100;j++)
            {
                c[i+j]+=a[i]*b[j];
                c[i+j+1]+=c[i+j]/10000;
                c[i+j]%=10000;
            }
        }
        return c;
    }
    void output()
    {
        int i;
        for (i=100;i>0;i--)
        {
            if (a[i]!=0) break;
        }
        printf("%d",a[i]);
        for (i--;i>=0;i--)
        {
            printf("%04d",a[i]);
        }
    }
};
int l[205],r[205];
bigint ans(1);
int size[205];
int get_size(int x)
{
    if (x==-1) return 0;
    return size[x];
}
void dfs(int x)
{
    if (x==-1) return;
    dfs(l[x]);
    dfs(r[x]);
    size[x]=1+get_size(l[x])+get_size(r[x]);
}
bigint c[205][205];
int main()
{
    freopen("cartesian.in","r",stdin);
    freopen("cartesian.out","w",stdout);
    int n;
    scanf("%d",&n);
    int i;
    for (i=0;i<=200;i++)
    {
        c[i][0]=bigint(1);
        int j;
        for (j=1;j<=i;j++)
        {
            c[i][j]=c[i-1][j]+c[i-1][j-1];
        }
    }
    for (i=0;i<n;i++)
    {
        scanf("%d%d",&l[i],&r[i]);
        l[i]--;
        r[i]--;
    }
    dfs(0);
    for (i=0;i<n;i++)
    {
        ans=ans*c[get_size(i)-1][get_size(l[i])];
    }
    ans.output();
    return 0;
}