点分树上的某个点和其某个子树在原树中的连接方式一般来说可以是由该点连向子树内任意一点，这样方案数即为所有子树大小之积。但有一种特殊情况是连接某点后导致编号最小的重心更换，只要去掉这种就行了，具体地可以直接暴力找，因为点分树只有log层，每个点最多被找log次。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 100010 #define P 1000000007 char getc(){char c=getchar();while ((c<‘A‘||c>‘Z‘)&&(c<‘a‘||c>‘z‘)&&(c<‘0‘||c>‘9‘)) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} 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^48),c=getchar(); return x*f; } int T,n,p[N],size[N],t,root,degree[N],ans; struct data{int to,nxt,len; }edge[N]; void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;} void dfs(int k) { size[k]=1; for (int i=p[k];i;i=edge[i].nxt) dfs(edge[i].to),size[k]+=size[edge[i].to]; } int find(int k,int root) { int cnt=k<root; for (int i=p[k];i;i=edge[i].nxt) cnt+=find(edge[i].to,root); return cnt; } void calc(int k) { for (int i=p[k];i;i=edge[i].nxt) { if ((size[edge[i].to]<<1)<size[k]) ans=1ll*ans*size[edge[i].to]%P; else ans=1ll*ans*(size[edge[i].to]-find(edge[i].to,k))%P; calc(edge[i].to); } } int main() { #ifndef ONLINE_JUDGE freopen("bzoj4835.in","r",stdin); freopen("bzoj4835.out","w",stdout); const char LL[]="%I64d\n"; #else const char LL[]="%lld\n"; #endif T=read(); while (T--) { n=read();read(); t=0;for (int i=1;i<=n;i++) p[i]=0,degree[i]=0;ans=1; for (int i=1;i<n;i++) { int x=read(),y=read(); addedge(x,y);degree[y]++; } for (int i=1;i<=n;i++) if (!degree[i]) root=i; dfs(root); calc(root); printf("%d\n",ans); } return 0; }
原文：https://www.cnblogs.com/Gloid/p/10009901.html