首先设 $f[x]$ 表示点分树上 $x$ 的子树内的方案数
发现对于 $x$ 的每个儿子 $v$ ，$x$ 似乎可以向 $v$ 子树内的每个节点连边，因为不管怎么连重心都不会变
显然是错的，题目描述中说如果有多个重心取编号最小的，所以如果 $v$ 的子树大小恰好为 $x$ 的子树大小的一半
那么 $x$ 只能向 $v$ 中编号大于 $x$ 的节点连边，找编号比较大的直接暴力找即可，因为点分树的深度是 $\log n$ 的
每个点最多被每个祖先枚举到一次，所以复杂度 $O(n \log n)$
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=1e5+7,mo=1e9+7; int T,n,m; int fir[N],from[N<<1],to[N<<1],cntt; inline void add(int a,int b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; } int f[N],sz[N]; bool vis[N]; int calc(int x,int k) { int res=x>k; for(int i=fir[x];i;i=from[i]) res+=calc(to[i],k); return res; } void dfs(int x) { sz[x]=f[x]=1; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; dfs(v); sz[x]+=sz[v]; } bool flag=!(sz[x]&1); int t=sz[x]>>1; for(int i=fir[x];i;i=from[i]) { int &v=to[i],cnt=0; if(flag && sz[v]==t) cnt=calc(v,x); else cnt=sz[v]; f[x]=1ll*f[x]*f[v]%mo*cnt%mo; } } int main() { T=read(); while(T--) { for(int i=1;i<=n;i++) fir[i]=vis[i]=0; cntt=0; n=read(),m=read(); for(int i=1;i<n;i++) { int a=read(),b=read(); add(a,b); vis[b]=1; } int rt=0; for(int i=1;i<=n;i++) if(!vis[i]) { rt=i; break; } dfs(rt); printf("%d\n",f[rt]); } return 0; }