[atARC087F]Squirrel Migration

对这棵树重心情况分类讨论：

1.若这棵树存在两个重心，分别记作$x$和$y$，如果将$(x,y)$断开，两棵子树大小都相同（都为$\frac{n}{2}$），此时$p_{i}$与$i$必然不同属于一个连通块中，证明如下：

考虑若$p_{i}$与$i$在一个连通块中，则必然有$p_{j}$和$j$也在同一个连通块中且与$i$不同，将其交换一定更优

将距离拆为两颗子树内部+$(x,y)$，即有$mx=2\sum dep_{i}(以(x,y)为根)+n$，方案数为$(\frac{n}{2}!)^{2}$

2.若这棵树仅有1个重心，类似于Distance Matching，若以重心为根，$mx=2\sum dep_{i}$

问题相当于要求任意$i$和$p_{i}$不在重心的同一个儿子中，考虑容斥，令集合$S$表示$i$和$p_{i}$在重心的同一个儿子中的$i$，$f_{S}$表示对应方案数

对$S$和$S$以外的的点分别计算（再相乘）：

1.对$S$以外，考虑$i\in S$，其实可以将$p_{i}$理解为$i$，换言之将$p_{j}=i$的位置改为$p_{j}=p_{i}$即可，因此剩下的点任意排列，方案数为$(n-|S|)!$

2.对$S$以内，即从子树中选$i$个，即为$\prod_{son}a_{son}!c(sz_{son},a_{son})$（$son$表示重心的儿子，$a_{son}$表示son子树内所选的节点个数）

由于$|S|=\sum_{son}a_{son}$，因此答案仅与$a_{i}$有关，对应答案为$(n-\sum_{son}a_{son})!\prod_{son}a_{son}!c(sz_{son},a_{son})^{2}$（对应的$|S|$有$\prod_{son}c(sz_{son},a_{son})$种）

令$f_{i}$表示当$\sum_{son}a_{son}=i$时$\prod_{son}c(sz_{son},a_{son})^{2}$的和，dp转移即可，时间复杂度为$o(n^{2})$（枚举子树和$a_{i}$的总量为$o(n)$），还可以用分治fft优化到$o(n\log^{2}n)$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 5005

 4 #define mod 1000000007

 5 struct ji{

 6     int nex,to;

 7 }edge[N<<1];

 8 vector<int>v;

 9 int E,n,m,x,y,ans,head[N],sz[N],fac[N],inv[N],f[N][N];

10 int sqr(int n){

11     return 1LL*n*n%mod;

12 }

13 int c(int n,int m){

14     return 1LL*fac[n]*inv[m]%mod*inv[n-m]%mod;

15 }

16 void add(int x,int y){

17     edge[E].nex=head[x];

18     edge[E].to=y;

19     head[x]=E++;

20 }

21 void dfs(int k,int fa){

22     int mx=0;

23     sz[k]=1;

24     for(int i=head[k];i!=-1;i=edge[i].nex)

25         if (edge[i].to!=fa){

26             dfs(edge[i].to,k);

27             mx=max(mx,sz[edge[i].to]);

28             sz[k]+=sz[edge[i].to];

29         }

30     if (max(mx,n-sz[k])<=n/2){

31         if (!x)x=k;

32         else y=k;

33     }

34 }

35 int main(){

36     fac[0]=inv[0]=inv[1]=1;

37     for(int i=1;i<N-4;i++)fac[i]=1LL*fac[i-1]*i%mod;

38     for(int i=2;i<N-4;i++)inv[i]=1LL*(mod-mod/i)*inv[mod%i]%mod;

39     for(int i=1;i<N-4;i++)inv[i]=1LL*inv[i]*inv[i-1]%mod;

40     scanf("%d",&n);

41     memset(head,-1,sizeof(head));

42     for(int i=1;i<n;i++){

43         scanf("%d%d",&x,&y);

44         add(x,y);

45         add(y,x);

46     }

47     x=y=0;

48     dfs(1,0);

49     if (y){

50         printf("%d",sqr(fac[n/2]));

51         return 0;

52     }

53     dfs(x,0);

54     v.push_back(0);

55     for(int i=head[x];i!=-1;i=edge[i].nex)v.push_back(sz[edge[i].to]);

56     m=v.size()-1;

57     f[0][0]=1;

58     int s=0;

59     for(int i=1;i<=m;i++){

60         for(int j=0;j<=s;j++)

61             for(int k=0;k<=v[i];k++)

62                 f[i][j+k]=(f[i][j+k]+1LL*fac[k]*sqr(c(v[i],k))%mod*f[i-1][j])%mod;

63         s+=v[i];

64     }

65     assert(s==n-1);

66     for(int i=0;i<n;i++){

67         int s=1LL*f[m][i]*fac[n-i]%mod;

68         if (i&1)s=mod-s;

69         ans=(ans+s)%mod;

70     }

71     printf("%d",ans);

72 }

巴特西

[atARC087F]Squirrel Migration

最新文章

热门文章