[??记录]AT3728 [ARC087D] Squirrel Migration
command_block
2021-05-07 14:57:03
**题意** ： 给出一棵 $n$ 个节点的树。
求使得 $\sum dis(i,p_i)$ 最大的排列 $p$ 的个数。
答案对 $10^9+7$ 取模。
$n\leq 5000$ ，时限$\texttt{5s}$。
------------
首先考虑如何求出 $\sum dis(i,p_i)$ 的最大值。
对每条边分别考虑贡献，设两侧的点数分别为 $s_1,s_2$ ，则这条边的贡献有上界 $2\min\{s_1,s_2\}$。
也可以构造出方案使得每条边的贡献达到上界。
以重心为根，对于每条边而言，深度较大的一侧则为点数较小的一侧。
记 $u$ 的子树大小为 $siz_u$ ，每条边 $u\rightarrow v$ （ $v$ 为较深一侧 ） 都要上下经过各 $siz_u$ 次。
对于每个点，寻找一个与自己处在根的不同分支的，未匹配的点，进行匹配即可。
（若某个点和同一个分支内的点匹配，则必然不优）
由于根的各个分支大小不超过整棵树的一半，故总能有这样的匹配。
接下来考虑计数。
- 只有一个重心
记第 $i$ 个分支的大小为 $c_i$。（这种情况下允许重心匹配自己）
问题可以转化为 ： 有 $n$ 个点，点有颜色（同一个分支即为同色），要为每个点连出一个出边（有向边），满足每条边两端不能同色。
考虑容斥， $f(k)$ 表示钦定 $k$ 条边两端同色，其余随意的方案数，则有 ：
$${\rm Ans}=\sum\limits_{i=0}(-1)^if(i)$$
接下来看 $f(k)$ 如何计算。可以先挑出 $k$ 条同色边，剩余的边随意，方案数是 $(n-k)!$。
对于第 $i$ 种颜色，钦定 $k$ 条同色边的方案数为 $\dbinom{c_i}{k}c_i^{\underline k}$
将各个颜色的方案卷积（背包）起来即可。复杂度为 $O(n^2)$。
若利用分治 $\rm FFT$ 则可以做到 $O(n\log^2n)$。
- 有两个重心
找出连接两个重心的边，两侧的点数都恰好是 $n/2$。
只需要两侧的点之间随意匹配即可，方案数为 $(n/2)!^2$。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#define pb push_back
#define ll long long
#define MaxN 5050
using namespace std;
vector<int> g[MaxN];
int n,rt,siz[MaxN];
void dfs(int u)
{
siz[u]=1;
for (int i=0,v;i<g[u].size();i++)
if (!siz[v=g[u][i]]){
dfs(v);
siz[u]+=siz[v];
}
if (!rt&&siz[u]*2>=n)rt=u;
}
const int mod=1000000007;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
t>>=1;a=a*a%mod;
}return ret;
}
ll fac[MaxN],ifac[MaxN];
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
}
ll F[MaxN],G[MaxN],S[MaxN];
int main()
{
scanf("%d",&n);Init(n);
for (int i=1,u,v;i<n;i++){
scanf("%d%d",&u,&v);
g[u].pb(v);g[v].pb(u);
}
dfs(1);int sav=rt;
for (int i=1;i<=n;i++)siz[i]=0;
dfs(rt);
bool fl=0;
for (int i=2;i<=n;i++)
fl|=(siz[i]*2==n);
if (fl){
printf("%lld",fac[n/2]*fac[n/2]%mod);
return 0;
}
int m=0;F[0]=1;
for (int j=0;j<g[sav].size();j++){
int c=siz[g[sav][j]];
for (int i=0;i<=m;i++){S[i]=F[i];F[i]=0;}
for (int k=0;k<=c;k++){
ll G=fac[c]*ifac[k]%mod*ifac[c-k]%mod*fac[c]%mod*ifac[c-k]%mod;
for (int i=0;i<=m;i++)
F[i+k]=(F[i+k]+S[i]*G)%mod;
}m+=c;
}
ll ans=0;
for (int i=0;i<=n;i++){
ll buf=F[i]*fac[n-i]%mod;
if (i&1)ans-=buf;else ans+=buf;
}printf("%lld",(ans%mod+mod)%mod);
return 0;
}
```