社区讨论

大佬玄关求调 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 条回复,欢迎继续交流。

正在加载回复...