[ARC087F] Squirrel Migration
给你一个 \(n\) 个节点的树，求一个 \(1\sim n\) 的排列\((p_1,p_2,\dots p_n)\)，使得 \(\sum dist(i,p_i)\) 最大。
求这样的排列个数。答案对 \(10^9+7\) 取模。
相当于对于每个点 \(i\)，找到一个 \(p_i\) 与之匹配（但是 \(p_i\) 可以去匹配别的点）（说废话）。
结论：所有点 \(i\) 与 \(p_i\) 在这颗树的重心的不同子树中（或者其中一个点是重心本身）。
证明：
- 一定存在一种构造使得 \(i\) 和 \(p_i\) 存在于不同的重心子树中。将以重心为根的每个点按照 dfs 序组成一个环，因为重心的任意一颗子树大小小于 $ \frac{n}{2}$，且这颗子树内的点在环上连续，所以一个点左侧第 \(\frac{n}{2}\) 个点一定不在这颗点所属子树内。
- 满足这一条件的构造中存在一种可以取到最大答案。考虑反证，假如存在一个点 \(i\) 和 \(p_i\) 在同一子树内，那么可以根据第一条，一定存在另一个点 \(j\) 和 \(p_j\) 在同一子树内，我们将 \(i\to p_j,j\to p_i\) 一定会比现在更优。证明这点只需要对 \(i\) 和 \(p_i\)，\(j\) 和 \(p_j\) 取 \(lca\)，更改后的路径长度即比原先多 \(2\) 倍的 \(lca\) 间的路径长度。
现在我们就是要求有多少种方案使得 \(i\) 与 \(p_i\) 在重心的不同子树中，这个并不好直接求，使用容斥。
定义 \(f_i\) 为排列中有 \(i\) 个点不合法的方案数，剩下的点任意匹配的方案数，答案即为：
\[ans=\sum_{i=0}^{n}(-1)^i\times f_i\times (n-i)! \]现在考虑如何求 \(f\)。从子树合并的角度考虑。
假设子树的大小为 \(x\)，其中有 \(k\) 个点满足 \(i\) 与 \(p_i\) 在同一子树中，那么其方案数为 \(\binom{x}{k}^2k!\)。意义是从中找出 \(k\) 个点，和 \(k\) 个与之匹配的点（所以平方），然后这 \(k\) 个点可以任意排列。
于是可以使用树形背包合并每个子树的答案。转移是朴素的。
\[f_i\gets \sum_{j=0}^{i} f_{i-j}\times \binom{siz_u}{j}^2\times j! \]具体的转移细节和实现见代码。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int>ttfa;
inline ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-')f=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x*f;
}
const int N=100005;
const ll MOD=1000000007;
int n,root,siz[N],fiz[N];
ll fac[N],ifc[N],dp[N],ans;
inline ll C(ll n,ll r){return fac[n]*ifc[r]%MOD*ifc[n-r]%MOD;}
vector<int>edge[N];
inline ll fpr(ll b,ll t=MOD-2,ll x=1){
for(;t;t>>=1,b=b*b%MOD)
if(t&1)x=x*b%MOD;
return x;
}
void dfs(int u,int f){
siz[u]=1,fiz[u]=0;
for(auto v:edge[u]){
if(v==f)continue;
dfs(v,u);
siz[u]+=siz[v];
fiz[u]=max(fiz[u],siz[v]);
}fiz[u]=max(fiz[u],n-siz[u]);
if(fiz[u]<fiz[root])root=u;
}
int main(){
n=read();
fac[0]=ifc[0]=1;
for(int i=1;i<=n;++i)fac[i]=fac[i-1]*i%MOD;
ifc[n]=fpr(fac[n]);
for(int i=n-1;i>=1;--i)ifc[i]=ifc[i+1]*(i+1)%MOD;
for(int i=1;i<n;++i){
int u=read(),v=read();
edge[u].push_back(v);
edge[v].push_back(u);
}
fiz[root=0]=n;dfs(1,0);dfs(root,0);
dp[0]=1ll;
for(auto v:edge[root]){
int s=siz[v];
for(int i=n;i>=0;--i){//背包
for(int j=1;j<=min(i,s);++j){
ll tmp=C(s,j)*C(s,j)%MOD*fac[j]%MOD;
dp[i]=(dp[i]+dp[i-j]*tmp%MOD)%MOD;
}
}
}
for(int i=0;i<=n;++i)
ans=(ans+((i&1)?-1ll:1ll)*dp[i]*fac[n-i]%MOD+MOD)%MOD;
printf("%lld\n",ans);
return 0;
}