cf995f

题意：
　给你最多n=3000个节点的树，让你用1-d（d<1e9）来给树编号，一个节点的号必须小于等于他的所有祖先，问你编号的方案数

// f(i,j)-> i子树中最大值为j的方案数 i<=n j<=d
// f(i,j) = prod(f(son,j))+f(i,j-1) 1<=t<=j
// 用数学归纳法证明f(i,j)关于j是一个最高次为i的多项式

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

typedef long long ll;
ll mod=1e9+7;

ll qpow(ll a,ll b,ll mod){
    ll ret=1;
    while(b){
        if(b&1) ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}

//  (mod%i)=== -mod/i*i
const ll maxn=3005;
ll fac_inv[maxn]={1,1};
void inv_ini(){
    for(ll i=0,fac=1;i<maxn;i++,fac=fac*i%mod) {
        fac_inv[i]=qpow(fac,mod-2,mod);
    }
}

ll prepre[maxn],suf[maxn],*pre=prepre+1;
ll getval(ll *y,ll n,ll x){// O(n) n次多项式有n+1项 y[0]...y[n] -> y[x]
    pre[-1]=suf[n+1]=1;
    for(ll i=0;i<=n;i++) pre[i]=pre[i-1]*(x-i+mod)%mod;
    for(ll i=n;i>=0;i--) suf[i]=suf[i+1]*(i-x+mod)%mod;
    ll ret=0;
    for(ll i=0;i<=n;i++) {
        ll up=pre[i-1]*suf[i+1]%mod;
        ll down=fac_inv[i]*fac_inv[n-i]%mod;
        ret=(ret+y[i]*up%mod*down)%mod;
    }
    return ret;
}

// f(i,j)-> i子树中最大值为j的方案数  i<=n j<=d
// f(i,j) = prod(f(son,j))+f(i,j-1) 1<=t<=j
// 用数学归纳法证明f(i,j)关于j是一个最高次为i的多项式

ll dp[maxn][maxn], f[maxn];
int main(){
    inv_ini();
    ll n,d;
    while(~scanf("%lld%lld",&n,&d)){
        for(ll i=2;i<=n;i++) scanf("%lld",f+i);
        for(ll i=n;i>=1;i--) {
            for(ll j=1;j<=n+1;j++) dp[i][j]=1;
        }

        for(ll i=n;i>=1;i--) {
            for(ll j=2;j<=n+1;j++) {
                dp[i][j]+=dp[i][j-1];
                dp[i][j]%=mod;

                dp[f[i]][j]*=dp[i][j];
                dp[f[i]][j]%=mod;
            }
        }
        // f(1) f(2) .. f(n+1)
        // g(0) g(1) .. g(n) -> g(x)=f(x+1)
        // f(x)=g(x-1)
        printf("%lld\n",getval(dp[1]+1,n,d-1));
    }
}