首页 题解

# Description

Luogu传送门

# Solution

首先我们计算出整棵树的 dfs\text{dfs} 序，然后一个点的祖先的 dfs\text{dfs} 序一定小于当前点的 dfs\text{dfs} 序。

我们把输入的关键点按照 dfs\text{dfs} 序从小到大排序，对于一个关键点 pip_i，所有不能和它放到同一组的点一定在它前面。

考虑依次加入每个关键点，假设 g(x)g(x) 为 xx 到根路径上的关键点个数，f(i,j)f(i, j) 表示把前 ii 个关键点分成 jj 组的方案数，那么有：

f(i,j)=max⁡{j−g(pi),0}×f(i−1,j)+f(i−1,j−1))f(i, j) = \max\{j - g(p_i), 0\} \times f(i - 1, j) + f(i - 1, j - 1))

前者是把 pip_i 放到其他组里的方案数，后者是 pip_i 自成一组的方案（其实类似于第二类斯特林数）。

那如何求 g(x)g(x) 呢？

每处理一个关键点打个标记，然后数 pip_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
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
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

namespace IO{
    inline int read(){
        int x = 0;
        char ch = getchar();
        while(!isdigit(ch)) ch = getchar();
        while(isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
        return x;
    }

    template <typename T> inline void write(T x){
        if(x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}
using namespace IO;

const int N = 1e5 + 200;
const int mod = 1e9 + 7;
int n, q, k, m, r;
int p[N], f[N], dp[N][310];
vector <int> g[N];

inline bool cmp(int x, int y){
    return f[x] < f[y];
}

int fa[N], dep[N], siz[N], son[N];

inline void dfs1(int x, int f){
    fa[x] = f, dep[x] = dep[f] + 1, siz[x] = 1;
    for(auto y : g[x]){
        if(y == f) continue;
        dfs1(y, x);
        siz[x] += siz[y];
        if(siz[y] > siz[son[x]]) son[x] = y;
    }
}

int top[N], dfn[N], tim;

inline void dfs2(int x, int topfa){
    top[x] = topfa, dfn[x] = ++tim;
    if(son[x]) dfs2(son[x], topfa);
    for(auto y : g[x])
        if(y != fa[x] && y != son[x]) dfs2(y, y);
}

int c[N];

inline void add(int x, int y){
    for(; x <= n; x += x & (-x)) c[x] += y;
}

inline int qry(int l, int r){
    int res = 0;
    for(; r; r -= r & (-r)) res += c[r];
    for(--l; l; l -= l & (-l)) res -= c[l];
    return res;
}

inline int query(int x, int y){
    int res = 0;
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        res += qry(dfn[top[x]], dfn[x]);
        x = fa[top[x]];
    }
    if(dfn[x] > dfn[y]) swap(x, y);
    res += qry(dfn[x], dfn[y]);
    return res;
}

inline void Clear(){
    for(int i = 1; i <= k; ++i){
        for(int j = 1; j <= min(i, m); ++j) dp[i][j] = 0;
        f[p[i]] = 0, add(dfn[p[i]], -1);
    }
}

signed main(){
    n = read(), q = read();
    for(int i = 1; i < n; ++i){
        int u = read(), v = read();
        g[u].pb(v), g[v].pb(u);
    }
    dfs1(1, 0), dfs2(1, 1);
    while(q--){
        k = read(), m = read(), r = read();
        for(int i = 1; i <= k; ++i) add(dfn[p[i] = read()], 1);
        for(int i = 1; i <= k; ++i) f[p[i]] = query(p[i], r) - 1;
        sort(p + 1, p + 1 + k, cmp);
        dp[1][1] = 1;
        for(int i = 2; i <= k; ++i)
            for(int j = 1; j <= min(i, m); ++j)
                dp[i][j] = (1ll * max(j - f[p[i]], 0) * dp[i - 1][j] + dp[i - 1][j - 1]) % mod;
        int ans = 0;
        for(int i = 1; i <= m; ++i) ans = (ans + dp[k][i]) % mod;
        write(ans), puts(""), Clear();
    }
}

更新于 阅读次数 次