链接：https://www.luogu.com.cn/problem/CF995F
题目描述：
树形结构，给每个节点分配工资[\(1\),\(d\)]，子节点不能超过父亲节点的工资,问有多少种分配方案。
题解：
首先我们可以想到\(O(nd)\)的\(dp\),但跑不过。
这时我们可以想将\(d\)优化掉,可将每一个点的方案数看作一个关于\(d\)的多项式，然后发现这样只会涉及到多项式卷积与"多项式前缀加"（即有一个多项式\(A\)，构造一个多项式\(B\)使得若任意非负整数\(d\)都有\(\sum_{i=1}^{n}A(d)=B(d)\))。
当然，暴力维护多项式是可行的，但是还有更简便的方法，因为最多时将每个节点的贡献乘起来，所以多项式最高次数是\(O(n)\)级别的。预处理\(d<=n\)的取值，然后这样就可以拉格朗日插值了算答案了。
代码：
#include<iostream>
#include<cstdio>
#define mod 1000000007
using namespace std;
struct node
{
int v,nxt;
};
node edge[6001];
long long len,head[3001],res,n,k,x[3001],y[3001],mul,mul2;
long long read()
{
char c=0;
long long sum=0;
while (c<'0'||c>'9')
c=getchar();
while ('0'<=c&&c<='9')
{
sum=sum*10+c-'0';
c=getchar();
}
return sum;
}
void add(int x,int y)
{
edge[++len].v=y;
edge[len].nxt=head[x];
head[x]=len;
return;
}
long long fast_pow(long long a,int b)
{
if (b==0)
return 1;
if (b&1)
return fast_pow(a*a%mod,b/2)*a%mod;
else
return fast_pow(a*a%mod,b/2);
}
long long dp[3001][3001];
long long f(long long k)
{
res=0;
for (int i=0;i<=n;++i)
{
mul=mul2=1;
for (int j=0;j<=n;++j)
if (i!=j)
{
mul=mul*(k-j)%mod;
mul2=mul2*(i-j)%mod;
}
res=(res+dp[1][i]*mul%mod*fast_pow(mul2,mod-2)%mod)%mod;
}
return (res+mod)%mod;
}
void dfs(int x)
{
for (int i=1;i<=n;++i)
dp[x][i]=1;
for (int i=head[x];i>0;i=edge[i].nxt)
{
dfs(edge[i].v);
for (int j=1;j<=n;++j)
dp[x][j]=dp[x][j]*dp[edge[i].v][j]%mod;
}
for (int i=2;i<=n;++i)
dp[x][i]=(dp[x][i-1]+dp[x][i])%mod;
return;
}
int main()
{
int x,y;
n=read(),k=read();
for (int i=2;i<=n;++i)
{
x=read();
add(x,i);
}
dfs(1);
printf("%lld\n",f(k));
return 0;
}