# Description
Luogu 传送门
# Solution
首先我们计算出整棵树的 序，然后一个点的祖先的 序一定小于当前点的 序。
我们把输入的关键点按照 序从小到大排序，对于一个关键点 ，所有不能和它放到同一组的点一定在它前面。
考虑依次加入每个关键点，假设 为 到根路径上的关键点个数， 表示把前 个关键点分成 组的方案数，那么有：
前者是把 放到其他组里的方案数，后者是 自成一组的方案（其实类似于第二类斯特林数）。
那如何求 呢？
每处理一个关键点打个标记，然后数 到根的标记个数。
先树剖一下，然后树状数组区间加区间查询即可。
#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(); | |
} | |
} |
