社区讨论
WA on 6pt实在调不动了,玄关求调,大佬救救我
CF1111ETree参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @ly8kktyh
- 此快照首次捕获于
- 2024/07/05 18:45 2 年前
- 此快照最后确认于
- 2024/07/05 20:32 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
#define swap(a,b) (a ^= b, b ^= a, a ^= b)
const int mod = 1000000007;
const int N = 100005;
int cnt, head[N];
struct edge{
int to, nxt;
}e[N << 1];
int n, q;
int u, v;
int k, m, r;
int dfn[N], dep[N], tot;
int f[N][23], tag[N], dp[N][305], dfnn[N], ct[N], all;
vector<int> vt[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;
dep[e[i].to] = dep[x] + 1;
f[e[i].to][0] = x;
dfs(e[i].to, x);
}
}
void init(){
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]) u = f[u][i];
if(u == v) return u;
for(int i = 20;i >= 0;i--) if(f[u][i] != f[v][i]) 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 dfs_V(int x, int from){
dfnn[x] = ++all;
for(int i = 0;i < vt[x].size();i++){
if(vt[x][i] == from) continue;
ct[vt[x][i]] += ct[x] + tag[x];
dfs_V(vt[x][i], x);
}
}
inline cmpp(int x, int y){
return dfnn[x] < dfnn[y];
}
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--){
cin >> k >> m >> r;
int q[N << 1], p[N], lca, len, sum;
for(int i = 1;i <= k;i++) cin >> q[i], p[i] = q[i], tag[q[i]] = 1;
sort(q + 1, q + 1 + k, cmp);len = k;//for(int i = 1;i <= k;i++) cout << p[i] <<" ";cout <<endl;
for(int i = 2;i <= k;i++) q[++len] = LCA(q[i], q[i - 1]);q[++len] = r;//for(int i = 1;i <= len;i++) cout << q[i] <<" ";cout <<endl;
sort(q + 1, q + 1 + len, cmp);
len = unique(q + 1, q + 1 +len) - q - 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);
}
//for(int i = 1;i <= len;i++){
// for(int j = 0;j < vt[q[i]].size();j++) cout << q[i] << " " << vt[q[i]][j] << endl;
//}
dfs_V(r, 0);
sort(p + 1, p + 1 + k, cmpp);
dp[1][1] = 1;
//for(int i = 1;i <= k;i++) cout << p[i] << " " << dfnn[p[i]] << "\n";
for(int i = 2;i <= k;i++)
for(int j = 1;j <= min(i, m);j++)
dp[i][j] = (dp[i - 1][j - 1] + (dp[i - 1][j] * (j - ct[p[i]])) % mod * (j - ct[p[i]] >= 0)) % mod;
//cout << dp[i][j] << (j == min(i, m) ? "\n" : " ");
for(int i = 1;i <= m;i++) sum = (dp[k][i] + sum) % mod;
cout << sum << endl;
for(int i = 1;i <= len;i++) tag[q[i]] = 0, vt[q[i]].clear(), dfnn[q[i]] = ct[q[i]] = 0;
for(int i = 1;i <= len;i++) for(int j = 1;j <= m;j++) dp[i][j] = 0;
all = sum = 0;
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...