题解 P4492 【[HAOI2018]苹果树】

· · 题解

感谢zhoutb2333dalao提供做法~

本题题解

首先我们会发现按照题目中的方法生成二叉树，生成第1个点的时候有1种选择，第二个点的时候有2种选择，第3个点的时候有3种选择……，所以生成N个点的二叉树一共有N!种生成方式……

因此我们事实上就是在求所有可能的树的树上点对的距离和

发现太难根本没法算……，因为我们考虑问题的方向错了，我们应该从边的角度来考虑问题……

对于一条边来讲，我们考虑他会被多少点对经过，这就是这条边对树上点对距离的贡献了，换句话讲，枚举点对求树上距离和，和枚举边求经过点对数量和，是等价的，假如说我们考虑点i的父亲边对树上点对距离和的贡献的话，显然只有子树内->子树外的点对才会产生贡献，因此，点i的父亲边对总距离和的贡献为

size_{i}(n-size_{i})

那么我们现在要统计所有可能生成的二叉树，那么我们还是可以枚举边，计算在所有不同二叉树中的贡献，只是我们此时发现似乎没有办法知道siz

题目只要求了(N^2)复杂度，我们可以枚举边的同时再枚举一维siz

事实上这样的话我们相当于枚举了每一个子树的所有可能形态，所以这样计数是准的，只不过原来的我们整棵树整棵树考虑的，现在是随便找一颗子树枚举所有可能形态考虑的

好了，现在我们钦定了点i和siz_{i}，那么siz_{i}(n-siz_{i})的贡献就已经可以确定了,然而呢，我们还需要考虑有多少中可能的树形态是保证了点i的子树siz为某一个定值，然后再乘上siz_{i}(n-siz_{i})的贡献就可以算出在这个情况下的答案了

我们此时可以仿照求合法序列数问题的做法来求合法树的个数，在序列问题中有一个非常常见的套路是取任意一个“分割点”然后分别考虑分割点左边和右边的情况，两个乘起来就是我们要求的序列个数

同理我们在树上也可以采取类似的套路，删掉一条边，考虑分开的两个联通块的方案数，两个乘起来就是合法树的个数了

那么我们现在考虑点i的子树中的情况，从树的形态来讲，一共有siz_{i}!中不同的形态，从树的点的编号来讲，一共有C_{n-i}^{siz_{i}-1}中不同的编号，因为我们至少需要保证子树中的点编号都要比i大……所以子树内的方案数是

siz_{i}!C_{n-i}^{siz_{i}-1}

之后我们再来考虑点i的子树外面的情况

首先在生成点i之前一共是有i!中不同的生成方式，然后我们在生成了点i之后是不可以生成点放在的i子树中的，所以后边的点有(i+1-2),(i+2-2),(i+3-2),………(n-size_{i}+1-2)中生成方式，化简下就是

i(i-1)(n-size_{i}-1)!

然后我们可以给这个函数打个表，当然，现场计算也没问题

所以子树内外的方案相乘就是总的方案数啦~，大概是

siz_{i}!C_{n-i}^{siz_{i}-1}i(i-1)(n-size_{i}-1)!

总之，我们最后的计算树上点对距离和的式子就是

\sum_{i=2}^{n}\sum_{siz=1}^{n-i+1}siz!C_{n-i}^{siz-1}siz(n-siz)(n-siz+1)!i(i-1)

然后我们就可以愉快的计算啦~

上代码~

#include<cstdio>
#include<algorithm>
using namespace std;const int N=2010;typedef long long ll;
ll mod;int n;ll dp[N][N];ll fac[N];ll c[N][N];ll res;
int main()
{
    scanf("%d%lld",&n,&mod);fac[0]=1;
    for(int i=0;i<=n;i++)c[i][i]=c[0][i]=1;//组合数 
    for(int i=0;i<=n;i++)for(int j=1;j<n;j++)c[j][i]=(c[j-1][i-1]+c[j][i-1])%mod;
    for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod;dp[1][1]=1;//阶乘 
    for(int i=2;i<=n;i++)for(int j=1;j<=i;j++)dp[i][j]=fac[i-2]*j%mod*(j-1)%mod;//打表下子树外部的方案数 
    for(int i=2;i<=n;i++)//n^2枚举计算 
        for(int j=1;j<=n-i+1;j++)
            (res+=fac[j]*c[j-1][n-i]%mod*j*(n-j)%mod*dp[n-j+1][i])%=mod;
    printf("%lld",res);return 0;//拜拜程序~ 
}