南京夜无电波讯号·题解
Lucyna_Kushinada
·
·
题解
存在比较直接的组合意义优化做法，不过应某人的要求，但是这里也介绍一下期望做法。
先定义一些东西，
\displaystyle V(T_n)=\sum_{i=1}^n size_i^2
\displaystyle f_n=\sum_{T_n\in U_n} V(T_n)
\displaystyle S(T_n)=\sum_{i=1}^n size_i
\displaystyle g_n=\sum_{T_n\in U_n} S(T_n)
组合做法的基本思路是拆贡献，分别对每个节点计算它取到某个 size 时的方案数，然后再累加起来。
本题考察的核心在于 size^2 的那个指数，而在组合做法中变为了无足轻重、画蛇添足的败笔，出题人需要好好反思，但这并不意味着期望做法没有思维启发性。
在期望做法的视角下，size^2 的那个指数就变得比较难以处理，于是想到求解整体的变化量 f_n-f_{n-1}，再递推求出答案，于是就有了 g_n 与 S(T_n)。
那么 $\displaystyle g_n=\sum_{T_n\in U_n} S(T_n)=\sum_{T_n\in U_n}\sum_{i=1}^n d_i$，还是不太好做，考虑平均贡献，也就是期望，转化为 $\displaystyle g_n=(n-1)!\sum_{i=1}^n E(d_i)$。
那么只需要求出 $E(d_i)$，有转移：
$$\displaystyle E(d_i)=\frac{\sum_{j=1}^{i-1} E(d_j)}{i-1}+1$$
记 $\displaystyle s_n=\sum_{i=1}^n E(d_i)$，则 $g_n=(n-1)!s_n$。
接下来考虑 $f_{n-1}\to f_n$ 的变化量，拆为 $(n-1)f_{n-1}$（每棵 $(n-1)$ 个节点树都有 $(n-1)$ 种加点方法变为 $n$ 个节点的树），和节点 $n$ 带来的新变化：其到根的路径上的每个节点的 $size$ 都会加 $1$，同时它自己会有 $1$ 的 $size$。
考虑推一推后者的式子：
$$\Delta=$$
$$\displaystyle \sum_{T_{n-1}}\sum_{i=1}^{n-1}[\sum_{u\in path(i,1)} [(size_u+1)^2-size_u^2]+1]$$
$$\displaystyle \sum_{T_{n-1}}\sum_{i=1}^{n-1}[\sum_{u\in path(i,1)} (2size_u+1)+1]$$
$$\displaystyle \sum_{T_{n-1}}\sum_{i=1}^{n-1}[2\times\sum_{u\in path(i,1)} size_u+d_i+1]$$
$$\displaystyle 2\sum_{T_{n-1}}\sum_{i=1}^{n-1}\sum_{u\in path(i,1)}size_u+ \sum_{T_{n-1}}\sum_{i=1}^{n-1}d_i+\sum_{T_{n-1}}\sum_{i=1}^{n-1}1$$
考虑 $size_u$ 那部分的实质，得到：
$$\displaystyle 2\sum_{T_{n-1}}\sum_{i=1}^{n-1}size_i^2+ g_{n-1}+(n-2)!\times (n-1)$$
$$\displaystyle 2f_{n-1}+ g_{n-1}+(n-1)!$$
于是得到最终的递推式，
$$f_n=$$
$$(n-1)f_{n-1}+\Delta$$
$$(n+1)f_{n-1}+g_{n-1}+(n-1)!$$
~完结撒花~。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define per(i,l,r) for(int i=(r);i>=(l);--i)
#define pr pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define bg(x) (x).begin()
#define ed(x) (x).end()
#define N 1000010
#define int long long
const int mod=1e9+7;
inline int qpow(int a,int b=mod-2){
int ans=1;
while(b){
if(b&1){
ans=ans*a%mod;
}
a=a*a%mod;
b>>=1;
}
return ans;
}
int n,fac[N],iv[N],s[N],g[N],f[N];
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n;
fac[0]=1;
rep(i,1,n){
fac[i]=fac[i-1]*i%mod;
}
iv[n]=qpow(fac[n]);
per(i,0,n-1){
iv[i]=iv[i+1]*(i+1)%mod;
}
rep(i,0,n){
iv[i]=iv[i]*fac[i-1]%mod;
}
rep(i,1,n){
s[i]=s[i-1]*iv[i-1]%mod+1;
s[i]=(s[i-1]+s[i])%mod;
g[i]=s[i]*fac[i-1]%mod;
}
f[1]=1;
rep(i,2,n){
f[i]=(i+1)*f[i-1]%mod+g[i-1]+fac[i-1];
f[i]%=mod;
}
cout<<f[n]<<'\n';
return 0;
}
```