HDU-6338 Problem G. Depth-First Search(计数)

Problem G. Depth-First Search

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 378    Accepted Submission(s): 73

 

Problem Description

Kazari is learning depth-first search. More precisely, she is doing an experiment about it.
Consider an unrooted tree with n vertices and an empty array called A.
She randomly chooses a vertex s as root and starts from s to walk around, following the rules below.
* When she enters a vertex x for the first time, she append x to A at once.
* If some adjacent vertex has not been visited, she randomly chooses one and walks into it.
* If all adjacent vertices have been visited,
* If she is at root, the experiment is done.
* If she is not at root, she walks into the vertex which is the most nearest to root.
Among all possible arrays that A is likely to be finally, Kazari wishes to count how many of them is lexicographically smaller than the given array B. Since the answer is too large, print it modulo 109+7.

Input

The first line of the input contains an integer T denoting the number of test cases.
Each test case starts with a positive integer n (∑n≤106), denoting the number of vertices.
The second line contains n integers B1,B2,...,Bn (1≤Bi≤n,∀i≠j,Bi≠Bj).
Each of next n−1 lines contains two integers u,v, representing an edge (u,v) on the tree.

Output

For each test case, print a non-negative integer denoting the answer modulo 109+7.

Sample Input

2 5 2 1 3 5 4 1 2 2 3 2 4 4 5 6 6 4 5 3 2 1 1 2 2 3 3 4 4 5 5 6

Sample Output

3 9

题意：一个n个节点的无根树和长度为n的序列A，要求随意从一个点开始DFS，问有多少种DFS方法使得DFS序列的字典序小于序列A

题解：当前节点为u，子节点个数为sz[u]时，可以走的方案树为sz[u]!，易知选定一个根节点后，DFS的总方案数就为，还可以知道每个点的子节点数是它的度数-1，根节点的子节点数就是它的度数。

首先考虑root，任何root编号小于A[0]的DFS方法一定是可行的。然后考虑root编号，此时需要走到root的一个子节点，易知其编号，然后可以分类讨论下：

1. 当编号<A[1]时，则接下来任意走都是字典序小于序列A的
2. 当编号=A[1]时，继续往下走，再与A[2]比较，依次类推

然后再计算一下方案数：设f[n] = n!，cnt[u][x]为u的子节点中编号小于x的节点数，val[u]为子树u的DFS方案数，易知，其中v是子树u中所有节点

为了简化计算，只考虑当前点是root的情况

1. 先看root的子节点是否有编号为A[1]的点
2. 如果有，（v是u的子节点），然后递归到编号为A[1]的点，回到第一步再找A[2]
3. 如果没有，（v是u的子节点），然后直接返回（因为字典序已经小于序列A，下面子节点任意走即可）

解释一下2中的式子（3的式子同2）：

如果选择先走任意一个编号小于A[1]的点，则之后一定可以任意走，相当于从cnt[u][A[1]]个点中选一个点放在第一个位置；然后剩下的sz[u] - 1个点就可以任意摆放，方案数为(sz[u] - 1)!，因为可以任意走，所以在子树中行走的方案数为，把这几项乘起来即可。

#include <bits/stdc++.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define x first
#define y second
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=a-1;i>=b;--i)
#define fuck(x) cout<<'['<<#x<<' '<<(x)<<']'
#define FIN freopen("in.txt","r",stdin);
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
const int mod = 1e9 + 7;
const int MX = 1e6 + 5;

ll pow (ll a, int b) {
    ll ret = 1;
    while (b) {if (b & 1) ret = ret * a % mod; a = a * a % mod; b >>= 1;}
    return ret;
}
inline ll mul (ll a, ll b, ll c) {return a * b % mod * c % mod;}

vector<int>E[MX];
inline void init (int n) {
    rep (i, 1, n + 1) E[i].clear();
}
struct Tree {
    int n;
    vector <int> T;
    void init (int _n) {
        n = _n;
        T.resize (n + 1);
        for (int i = 0; i <= n; i++) T[i] = 0;
    }
    void add (int x, int v) {
        for (int i = x; i <= n; i += i & -i) T[i] += v;
    }
    int sum (int x) {
        if (x > n) x = n;
        int ret = 0;
        for (int i = x; i > 0; i -= i & -i) ret += T[i];
        return ret;
    }
} t[MX];
int n, a[MX];
ll f[MX], invf[MX], d, ans, index;
ll val[MX], inv[MX];
int solve (int u, ll v) {
    index++; ll sum = 1;
    rep(i, 0, E[u].size()) sum = sum * val[E[u][i]] % mod;
    per(i, E[u].size(), 0) {
        int nxt = lower_bound (E[u].begin(), E[u].end(), a[index + 1]) - E[u].begin();
        int cnt = t[u].sum (nxt);
        ans = (ans + mul (sum, f[i], v) * cnt) % mod;
        if (nxt == E[u].size() || E[u][nxt] != a[index + 1]) return 1;
        t[u].add (nxt + 1, -1);
        sum = sum * inv[E[u][nxt]] % mod;
        if (solve (E[u][nxt], mul (v, f[i], sum) ) ) return 1;
    }
    return 0;
}
void dfs (int u, int pre) {
    if (pre > 0) E[u].erase(find(E[u].begin(), E[u].end(), pre));
    val[u] = f[E[u].size()];
    t[u].init (E[u].size());
    rep(i, 0, E[u].size()) t[u].add (i + 1, 1);
    if(!E[u].empty()) {
        sort (E[u].begin(), E[u].end() );
        for (auto v : E[u]) {
            dfs (v, u);
            val[u] = val[u] * val[v] % mod;
        }
    }
    inv[u] = pow (val[u], mod - 2);
}
int main() {
    //FIN;
    f[0] = 1; rep (i, 1, MX) f[i] = f[i - 1] * i % mod;
    invf[MX - 1] = pow (f[MX - 1], mod - 2);
    per (i, MX - 1, 0) invf[i] = invf[i + 1] * (i + 1) % mod;
    int T; cin >> T;
    for(int cas = 1; cas <= T; cas++) {
        scanf ("%d", &n);
        init(n);
        rep (i, 0, n) scanf ("%d", &a[i]);
        rep (i, 1, n) {
            int u, v;
            scanf ("%d%d", &u, &v);
            E[u].push_back (v);
            E[v].push_back (u);
        }
        a[n] = 0, d = 1, ans = 0;
        rep (i, 1, n + 1) d = d * f[E[i].size() - 1] % mod;
        rep (i, 1, a[0]) ans = (ans + mul(d, f[E[i].size()], invf[E[i].size() - 1])) % mod;
        index = -1;
        dfs(a[0], -1);
        solve (a[0], 1);
        printf ("%lld\n", ans);
    }
    return 0;
}