社区讨论

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 条回复,欢迎继续交流。

正在加载回复...