典型例题

题目大意：

有 nn 个人，编号为 11 至 n(n≤105)n(n\le10^5) 。
除了编号为 11 的人，每个人都有自己的父亲。
求出有多少种排队的方式，使得每个人的父亲都排在他的前面。
方案数对 109+710^9+7 取模。

这类题目其实类似于dp的思想，就是统计方案数我们可以考虑是否可以去除他的一些后效性，然后将子树的数据汇聚到父节点来统计，使得复杂度为dfs枚举点的 Θ(n)\Theta(n) 乘上计算的 Θ(1)\Theta(1) 或者 Θ(log⁡2n)\Theta(\log_2n) 。

那对于这道题来说，我们可以发现子树之间是没有影响的，也就是说，只要保持好每一个子树内部的顺序，子树之间怎么穿插都可以。

不同子树内部顺序的组合比较好算，就是把他们每个自己的方案数乘起来就行，唯一的难点在于怎么处理穿插可以产生的不同方案数。

组合数插板法似乎并不适用，这里有一个比较易于理解的办法，随便放的情况除掉乱了子树内部顺序的情况就是合格的情况，即总的排列（也就是总点数-1的阶乘）除以每棵子树大小的阶乘（也就是去掉所有乱的情况）。

那我们就可以得到方案数的计算方法：

f(x)=(∏y∈sonxf(y))∗(sizex−1)!∏y∈sonxsizey!f(x)=\cfrac{(\prod_{y\in son_x}{f(y)})*(size_x-1)!}{\prod_{y\in son_x}size_y!}

这样一来，正常的dfs统计即可，时间复杂度就是枚举树乘上快速幂求逆元的 Θ(nlog⁡2n)\Theta(n\log_2n)

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
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, fa[1000050], head[1000050], cnt = 1, sz[1000050], ans[1000050], mod = 1e9 + 7, jc[1000050];
struct edge {
    int to, next;
} e[3000000];
void make(int u, int v) {
    e[cnt].next = head[u];
    e[cnt].to = v;
    head[u] = cnt++;
}
ll ksm(ll c, ll x) {
    if (c == 0)
        return 1;
    if (c == 1)
        return x;
    if (c % 2)
        return ksm(c / 2, x * x % mod) * x % mod;
    return ksm(c / 2, x * x % mod);
}
void dfs(ll x) {
    ans[x] = 1;
    for (int i = head[x]; i; i = e[i].next) {
        if (e[i].to == fa[x])
            continue;
        dfs(e[i].to);
        ans[x] = ((ans[x] * ans[e[i].to]) % mod * ksm(mod - 2, jc[sz[e[i].to]])) % mod;
        sz[x] += sz[e[i].to];
    }
    ans[x] = (ans[x] * jc[sz[x]]) % mod;
    sz[x]++;
}
int main() {
    scanf("%lld", &n);
    ll u, v;
    jc[0] = jc[1] = 1;
    for (int i = 2; i <= 1000010; i++) {
        jc[i] = jc[i - 1] * i % mod;
    }
    for (int i = 1; i < n; i++) {
        scanf("%lld%lld", &u, &v);
        fa[u] = v;
        make(v, u);
    }
    dfs(1);
    printf("%lld", ans[1]);
    return 0;
}

变式一

要是需要求任意一点为根的答案而数据范围不变呢？

对于这类“换根”题目我们一般正常就会联想到树上面相邻节点信息的小复杂度转移（譬如Θ(1)\Theta(1)或Θ(log⁡2n)\Theta(\log_2n)）

这道题也不例外——

朴素一点的做法：和之前一样求完一个钦定的根的答案以后，我们用这个钦定的根的答案向其他点去推，在换根的过程中发生关系变换的其实只有……

似乎有点不对劲对吧，一开始转换还行，但到后面就会变得逐渐复杂，难以思考，这里提供一个简单一点的思路——

由于叶子节点的方案数都是1，再将式子里的儿子的信息换成儿子的式子，最终我们得到的总的计算式是这样的：

f(x)=n!∏i≠rootsizeif(x)=\cfrac{n!}{\prod_{i\neq root}size_i}

那么这道题的解决思路也就明了了，转移无非就是乘上两个数再除去两个数（抵消后就只剩乘一个除一个了）。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n,head[1000000],cnt=1,sz[1000000],ans[1000000],ct[1000000],jc[1000000],mod=1e9+7;
struct edge{
	ll to,next;
}e[1000000];
void make(ll u,ll v){
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt++;
}
ll ksm(ll c,ll x){
	if(c==0)return 1;
	if(c%2)return ksm(c/2,x*x%mod)*x%mod;
	return ksm(c/2,x*x%mod);
}
void dfs1(ll x,ll fa){
	ct[x]=1;
	for(int i=head[x];i;i=e[i].next){
		if(e[i].to==fa)continue;
		dfs1(e[i].to,x);
		sz[x]+=sz[e[i].to];
		ct[x]=((ct[x]*ct[e[i].to])%mod*ksm(mod-2,jc[sz[e[i].to]]))%mod;
	}
	ct[x]=(ct[x]*jc[sz[x]])%mod;
	sz[x]++;
}
void dfs2(ll x,ll fa){
	if(x!=1){
		ans[x]=ans[fa]*ksm(mod-2,n-sz[x])%mod*sz[x]%mod;
	}
	for(int i=head[x];i;i=e[i].next){
		if(e[i].to==fa)continue;
		dfs2(e[i].to,x);
	}
}
int main(){
	scanf("%lld",&n);
	ll u,v;
	jc[0]=jc[1]=1;
	for(int i=2;i<=1000000;i++)jc[i]=jc[i-1]*i%mod;
	for(int i=1;i<n;i++){
		scanf("%lld%lld",&u,&v);
		make(u,v);
		make(v,u);
	}
	dfs1(1,0);
	ans[1]=ct[1];
	dfs2(1,0);
	for(int i=1;i<=n;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}