题意：

定义一个无根树的权值为所有点的度数的和，求有标号的n个点形成的所有森林的权值的和。

Solution:

比赛时脑抽，考完五分钟后过了...

由prufer序列的结论可得，对于n个点的无根树，可以形成个不同的树，我们记他的值为,那么对于n个点的森林的个数，我们可以求得DP式子：

可以看成将第n个点加入时，选择i个点和他形成一棵树。

接着我们再定义一个n个点能形成的所有无根树的权值和为，可以再次推出DP式子：

这里我们枚举每一个点i，枚举这个点的度数d，根据prufer序列的性质，第i个点度数为d的贡献可以看成与序列中有且仅有d-1个i的方案数之积。

注意到这里i没有用，所以式子可以改为：

(比赛的时候没有发现...想了半天如何简化)

最后，我们假设n个点的形成的森林的权值和为，类似于求的方法，我们每次将第n个点加入时，选择i个点和他形成一棵树，这样可以得到DP式子：

解释一下后面那坨式子的含义：选择i个点和第n个点形成一个有i+1个点的树，与之相对应，其他的点能形成f(n-i-1)中森林，对于每一种形成方式，都能得到A(i+1)的权值贡献，因此他们需要相乘，前面的式子同理。

这样我们预处理出F(n)，就能O(1)查答案了。

讲的比较粗糙，错误之处还请大佬指正。

代码：

#include<cstdio>
#include<iostream>
using namespace std;
int n,num[100010];
int a[100010];
int C[5010][5010],A[5010],F[5010],f[5010];
int st[5010];
int T,mod;
int fast_pow(int x,int a)
{
    int ans=1;
    for (;a;x=1ll*x*x%mod,a>>=1)
        if (a&1) ans=1ll*ans*x%mod;
    return ans;
}
int main()
{
    scanf("%d%d",&T,&mod);
    C[0][0]=1;
    for (int i=1;i<=5000;i++)
    {
        C[0][i]=1;
        for (int j=1;j<=i;j++)
            C[j][i]=(1ll*C[j][i-1]+C[j-1][i-1])%mod;
    }
    st[0]=st[1]=1;
    for (int N=1;N<=5000;N++)
    {
        for (int d=1;d<=N-1;d++)
        {
            A[N]=(1ll*d*d*C[d-1][N-2]%mod*fast_pow(N-1,N-2-d+1)+A[N])%mod; 
        }
        A[N]=1ll*N*A[N]%mod;
        if (N>1) st[N]=fast_pow(N,N-2);
    }
    f[0]=1;f[1]=1;
    for (int i=2;i<=5000;i++)
    {
        for (int j=0;j<i;j++)
            f[i]=(1ll*C[j][i-1]*f[i-j-1]%mod*st[j+1]+f[i])%mod;
    }
    for (int N=2;N<=5000;N++)
            for (int i=1;i<=N;i++)
            {
                F[N]=(1ll*C[i-1][N-1]*((1ll*st[i]*F[N-i]%mod+1ll*f[N-i]*A[i]%mod)%mod)+F[N])%mod;
            }
    while (T--)
    {
        scanf("%d",&n);

        printf("%d\n",F[n]);
    }
}