【组合计数】树上拓扑序 UVA11174 Stand in a Line

板子题：
https://www.luogu.com.cn/problem/UVA11174

分析

整个图形成了一片森林，我们记一棵树（根节点记为 (root)）的排序方案数为 (f[root])。

我们记 (root) 以下的子节点（即它们的父节点为 (root)）为 (c_1,c_2...c_k)。

方便起见，记 (sz[u]) 为以其为根的子树大小。

我们看看如何选取可以构成一个合法的序列：

首先序列第一个元素必然是根 (root)。

对子树内部的点进行排序，由乘法原理知一定有 (prod_{i=1}^k f[c_i]) 种方案。

假设每棵子树内部的点已经排好一定的顺序，那么每个子树内的点都可以看成是相同的元素，因此排列计数的方案数为 (frac{(sz[root]-1)!}{prod_{i=1}^k sz[c_i]!})。

因此由乘法原理，总共的方案数为：

[f[root] = prod_{i=1}^k f[c_i] imes frac{(sz[root]-1)!}{prod_{i=1}^k sz[c_i]!} ]

假设 (c_i) 有 (k_i') 个子节点（记为 (c'_j)），类似地有：

[f[c_i] = prod_{j=1}^{k_i'} f[c'_j] imes frac{(sz[c_i]-1)!}{prod_{i=1}^{k_i'} sz[c'_j]!} ]

对所有节点求积，即得

[f[root] =frac{(sz[root]-1)!}{prod sz[u]} ]

其中 (u) 代表除了根以外的所有节点。

代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long

using ll=long long;

const int N=4e4+5, M=N<<1, mod=1e9+7;

int n, m;

struct node{
	int to, next;
}e[M];

int h[N], tot;

void add(int u, int v){
	e[tot].to=v, e[tot].next=h[u], h[u]=tot++;
}

bool vis[N];
int sz[N];

void dfs(int u, int fa){
	sz[u]=1;
	for(int i=h[u]; ~i; i=e[i].next){
		int go=e[i].to;
		if(go==fa) continue;
		
		dfs(go, u);
		sz[u]+=sz[go];
	}	
}

ll fpow(ll x,ll p)
{
    ll res=1;
    for(;p;p>>=1,x=x*x%mod)
        if(p&1)res=res*x%mod;
    return res%mod;
}

ll inv(ll x){
	return fpow(x,mod-2)%mod;
}

ll fac[N];

void init(){
	fac[0]=1;
	for(int i=1; i<N; i++) fac[i]=fac[i-1]*i%mod;
}

ll C(ll a, ll b){
	return fac[a]*inv(fac[b])%mod*inv(fac[a-b])%mod;
}

signed main(){
	init();
	
	int T; cin>>T;
	while(T--){
		memset(h, -1, sizeof h), tot=0;
		memset(vis, 0, sizeof vis);
		cin>>n>>m;
		
		for(int i=0; i<m; i++){
			int u, fa; cin>>u>>fa;
			add(fa, u), add(u, fa);
			vis[u]=true;
		}
		
		for(int i=1; i<=n; i++) if(!vis[i]) add(i, 0), add(0, i);
		
		dfs(0, -1);
		
		int t=1;
		
		for(int i=1; i<=n; i++) t=t*inv(sz[i])%mod; 
		
		cout<<fac[sz[0]-1]*t%mod<<endl;
	}	
	return 0;
}