题解 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)$ 然后我们就可以愉快的计算啦~ 上代码~ ```C #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;//拜拜程序~ } ```