[ARC087D] Squirrel Migration

瞎扯：考虑 \(dis(x,y)=dep_x+dep_y-2dep_{lca(x,y)}\)，于是让 \(lca\) 最小即可。

易知如果根节点的最大的子树不超过一半，那么所有的 \(lca\) 都可以在根。如果大于一半呢，递归这棵子树吗？好像不太好做的样子。

正解：我在想马呢。直接选中心做根，完事了。后面的计算可以考虑容斥。所以这题凭什么铜牌？

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int maxn=2e5+10;
const int mod=1e9+7;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int N=5e3+10;
int n,m,mx,rt,R,ans;
int beg[N],nex[N<<1],to[N<<1],e;
inline void add(int x,int y){
	e++;nex[e]=beg[x];beg[x]=e;to[e]=y;
	e++;nex[e]=beg[y];beg[y]=e;to[e]=x;
}
int siz[maxn];
inline void dfs(int x,int fa){
	siz[x]=1;int Mx=0;
	for(int i=beg[x];i;i=nex[i]){
		int t=to[i];
		if(t==fa)continue;
		dfs(t,x);
		siz[x]+=siz[t];
		Mx=max(Mx,siz[t]);
	}Mx=max(Mx,n-siz[x]);
	if(Mx<mx)mx=Mx,rt=x;
}
int st[maxn],top,f[N],dp[N];
int fac[N],ifc[N],inv[N];
inline int com(int x,int y){
	if(x<y)return 0;
	return 1ll*fac[x]*ifc[y]%mod*ifc[x-y]%mod;
}
int main(){
	n=read();mx=inf;
	inv[1]=fac[0]=ifc[0]=1;
	for(int i=2;i<=n;i++)
		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
	for(int i=1;i<=n;i++)
		fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=1;i<=n;i++)
		ifc[i]=1ll*ifc[i-1]*inv[i]%mod;
	for(int i=1,x,y;i<n;i++)
		x=read(),y=read(),add(x,y);
	dfs(1,0);R=rt;dfs(rt,0);
	for(int i=beg[R];i;i=nex[i])
		st[++top]=siz[to[i]];
	dp[0]=1;f[0]=0;
	for(int i=1;i<=top;i++){
		for(int j=1;j<=st[i];j++)
			f[j]=1ll*com(st[i],j)*com(st[i],j)%mod*fac[j]%mod;
		for(int j=n;j>=0;j--)
			for(int k=0;k<=st[i]&&k<=j;k++)
				dp[j]=(dp[j]+1ll*dp[j-k]*f[k])%mod;
	}
	for(int i=0;i<=n;i++)
		if(~i&1)ans=(ans+1ll*dp[i]*fac[n-i])%mod;
		else ans=(ans+mod-1ll*dp[i]*fac[n-i]%mod)%mod;
	printf("%d\n",ans);
	return 0;
}