社区讨论
大佬玄关求调 wa on 6pt,球球了
CF1111ETree参与者 1已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @ly70j716
- 此快照首次捕获于
- 2024/07/04 16:36 2 年前
- 此快照最后确认于
- 2024/07/04 18:47 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
const long long mod = 1000000007;
#define swap(a, b) (a ^= b, b ^= a, a ^= b)
int head[N], cnt;
struct edge{
int to, nxt;
}e[N << 1];
int n, q;
int u, v;
int k, m, r;
int dfn[N], dep[N], fa[N], tot;
int f[N][23];
int sum[N];
vector<int> vt[N];
long long dp[N][305];
bool tag[N];
void add(int u, int v){
e[++cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
void dfs(int x, int from){
dfn[x] = ++tot;
for(int i = head[x];i;i = e[i].nxt){
if(e[i].to == from) continue;
if(!dep[e[i].to]) dep[e[i].to] = dep[x] + 1;
fa[e[i].to] = x;
dfs(e[i].to, x);
}
}
void init(){
for(int i = 1;i <= n;i++) ::f[i][0] = fa[i];
for(int i = 1;i <= 20;i++){
for(int j = 1;j <= n;j ++){
::f[j][i] = ::f[::f[j][i - 1]][i - 1];
}
}
}
int LCA(int u, int v){
if(dep[u] < dep[v]) swap(u, v);
for(int i = 20;i >= 0;i--){
if(dep[f[u][i]] < dep[v]) continue;
u = f[u][i];
}
if(u == v) return u;
for(int i = 20;i >= 0;i--){
if(f[u][i] == f[v][i]) continue;
u = f[u][i], v = f[v][i];
}
return f[u][0];
}
inline bool cmp(int x, int y){
return dfn[x] < dfn[y];
}
void dfs2(int x, int from){
for(int i = 0;i < vt[x].size();i++){
if(vt[x][i] == from) continue;
sum[vt[x][i]] = sum[x] + tag[x];
//if(tag[x]) cout << vt[x][i] << endl;
dfs2(vt[x][i], x);
}
}
int main(){
cin >> n >> q;
for(int i = 1;i < n;i ++){
cin >> u >> v;
add(u, v);
add(v, u);
}dep[1] = 1;
dfs(1, 0);
init();
while(q--){
int q[N << 1], p[N << 1], len, lca;
long long ans = 0;
cin >> k >> m >> r;
for(int i = 1;i <= k;i++) cin >> q[i];
sort(q + 1 , q + 1 + k, cmp);len = k;
for(int i = 1;i <= k;i ++) p[i] = q[i];//复制
for(int i = 2;i <= k;i++) q[++len] = LCA(q[i - 1], q[i]);q[++len] = r;
sort(q + 1 , q + 1 + len);
len = unique(q + 1, q + 1 + len) - q - 1;
sort(q + 1 , q + 1 + len, cmp);
//for(int i = 1;i <= len;i ++) cout << q[i] << " ";cout <<endl;
for(int i = 1;i <= k;i++) tag[p[i]] = 1;//标记
for(int i = 2;i <= len;i++){//建虚树
lca = LCA(q[i], q[i - 1]);
vt[lca].push_back(q[i]);
vt[q[i]].push_back(lca);
}sum[r] = 0;
dfs2(r, 0);
//for(int i = 1;i <= n;i++) cout << sum[i] <<" ";cout<<endl;
dp[1][1] = 1;
for(int i = 2;i <= k;i++){//cout << i << ' ';
for(int j = 1;j <= min(i, m);j++){
dp[i][j] = (dp[i - 1][j - 1] + 1ll * dp[i - 1][j] * (j - sum[p[i]]) * (j - sum[p[i]] >= 0) % mod) % mod;
//cout << dp[i][j] <<" dp " << sum[p[i]] << " dp ";
}//cout<< "\n";
}
for(int i = 1;i <= m;i ++) ans = (ans + dp[k][i]) % mod;
cout << ans << endl;
for(int i = 1;i <= n;i++) sum[i] = 0, tag[i] = 0;
for(int i = 1;i <= n;i++) vt[i].clear();
for(int i = 0;i <= len + 10;i++){
for(int j = 0;j <= m + 1;j++){
dp[i][j] = 0;
}
}
}
return 0;
}
回复
共 1 条回复,欢迎继续交流。
正在加载回复...