[??记录]AT3728 [ARC087D] Squirrel Migration

· · 个人记录

题意 ： 给出一棵 n 个节点的树。

求使得 \sum dis(i,p_i) 最大的排列 p 的个数。

答案对 10^9+7 取模。

------------ 首先考虑如何求出 $\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)。

#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;
}