【树形DP】树上拓扑序计数

树上拓扑序计数|树形DP

较好的观感

题目链接：
https://ac.nowcoder.com/acm/contest/38630/F

思路

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

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

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

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

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

例子：u节点有四颗子树，子树大小分别为a, b, c, d，则方案数为：
$$\begin{gathered} f[u]=f[a]\ast f[b]\ast f[c]\ast f[d]\ast C(a+b+c+d,a)\ast C(b+c+d,b)\ast C(c+d,c) \\ =f[a]\ast f[b]\ast f[c]\ast f[d]\ast \frac{(a+b+c+d)!}{a!(b+c+d)!}\ast \frac{(b+c+d)!}{b!(c+d)!}\ast \frac{(c+d)!}{c!d!} \\ =f[a]\ast f[b]\ast f[c]\ast f[d]\ast \frac{(a+b+c+d)!}{a!b!c!d!} \end{gathered}$$

推广到一般树：
$$f[u]=(\prod _{v\in son(u)}f[v])\ast \frac{(sz[u]-1)!}{\prod _{v\in son(u)}sz[v]!}$$
换一下形式：
$$f[u]=(sz[u]-1)!\ast \prod _{v\in son(u)}\frac{f[v]}{sz[v]!}$$

拓扑序数量还可以这样计算：
$$n!\ast \prod _{i=1}^n\frac{1}{sz[i]}$$

代码1

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

代码2

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143

拓扑序计数相关题目：

HDU4661 ： http://acm.hdu.edu.cn/showproblem.php?pid=4661