树上拓扑序计数

至至子的公司排队

https://ac.nowcoder.com/acm/contest/38630/F

F

较好的观感

树上拓扑序计数|树形DP

https://ac.nowcoder.com/acm/contest/38630/F

思路

每个公司是一棵树，然后每个公司可以看做连在一个虚拟的根上。每个公司的计算方案实际上就是计算这棵树的拓扑序的个数。用树形DP求解。

$f [u]$ : 以u为根的子树的拓扑序数

$s z [u]$ ：以u为根的子树的大小（节点的数量）

当树为二叉树时，将两个子树v1,v2进行合并：即先把各子树的方案数乘起来算出总方案，然后考虑各子树元素的相对排列顺序，即在总的节点个数中选sz[v1]排在前面的sz[v1]个位置，剩下的排在后面，保证每颗子树的相对拓扑序不变。

f[u] = f[v1] \cdot f[v2] \cdot C(sz[v1] + sz[v2], sz[v1])

例子：u节点有四颗子树，子树大小分别为a, b, c, d，则方案数为：

$f[u] = f[a]\cdot f[b]\cdot f[c]\cdot f[d]\cdot C(a+b+c+d, a)\cdot C(b+c+d, b)\cdot C(c+d,c)$

$=f[a]\cdot f[b]\cdot f[c]\cdot f[d]\cdot \frac{(a+b+c+d)!}{a!(b+c+d)!}\cdot \frac{(b+c+d)!}{b!(c+d)!}\cdot \frac{(c+d)!}{c!d!}$

$=f[a]\cdot f[b]\cdot f[c]\cdot f[d]\cdot \frac{(a+b+c+d)!}{a!b!c!d!}$

推广到一般树：

f[u] = (\prod \limits_{v \in son(u)} f[v] ) \cdot \frac{(sz[u] - 1)!}{\prod \limits_{v \in son(u)}sz[v]!}

换一下形式：

f[u] = (sz[u] - 1)! \cdot \prod \limits_{v \in son(u)} \frac{f[v]}{sz[v]!}

拓扑序数量还可以这样计算：

n! \cdot \prod \limits_{i = 1} ^ n \frac{1}{sz[i]}

代码1

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
const int N = 1e5 + 5, M = N;
const int mod = 1e9 + 7;

ll fac[N], inv[N];
ll ksm(ll a, ll b)
{
	ll res = 1;
	while(b)
	{
		if(b & 1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res % mod;
}
void solve()
{
	int n;
	cin >> n;

	ll ans = 1, tot = 1;
	int cnt = 0;
	for(int i = 1; i <= n; i++)
	{
		int c;
		cin >> c;
		cnt += c;
		vector<vi> g(c);

		for(int j = 1; j < c; j++)
		{
			int u;
			cin >> u;
			u--;
			g[u].push_back(j);
		}

		vi sz(c, 1);
		vl f(c, 1);
		function<void(int)> dfs = [&](int u)
		{
			for(auto v : g[u])
			{
				dfs(v);
				sz[u] += sz[v];
				(f[u] *= f[v] * inv[sz[v]] % mod) %= mod;
			}
			(f[u] *= fac[sz[u] - 1]) %= mod;
		};
		dfs(0);
		(tot *= f[0] * inv[c] % mod) %= mod;
	}
	ans = ans * tot % mod * fac[cnt] % mod;
	cout << ans << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	fac[0] = 1;
	for(int i = 1; i < N; i++)
		fac[i] = fac[i - 1] * i % mod;
	inv[N - 1] = ksm(fac[N - 1], mod - 2);
	for(int i = N - 2; i >= 1; i--)
		inv[i] = (i + 1) * inv[i + 1] % mod;

	int t;
	t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

代码2

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using arr = array<int, 3>;
using vi = vector<int>;
using vl = vector<ll>;
const int N = 1e5 + 5, M = N;
const int mod = 1e9 + 7;

// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += mod;
    }
    if (x >= mod) {
        x -= mod;
    }
    return x;
}
template<class T>
T power(T a, ll b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(ll x) : x(norm(x % mod)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(mod - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, mod - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = ll(x) * rhs.x % mod;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        ll v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};

void solve()
{
	int n;
	cin >> n;

	Z ans = 1;
	int tot = 0;
	for(int i = 0; i < n; i++)
	{
		int c;
		cin >> c;

		for(int j = 0; j < c; j++)
			ans *= ++tot;

		vector<vi> g(c);
		for(int j = 1; j < c; j++)
		{
			int u;
			cin >> u;
			u--;
			g[u].push_back(j);
		}

		vi sz(c, 1);

		function<void(int)> dfs = [&](int u)
		{
			for(auto v : g[u])
			{
				dfs(v);
				sz[u] += sz[v];
			}
			ans /= sz[u];
		};
		dfs(0);
	}

	cout << ans << "\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t;
	t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}