蒟蒻初学虚树,#1~#10MLE,求调
查看原帖
蒟蒻初学虚树,#1~#10MLE,求调
461359
huangrenheluogu楼主2023/6/25 13:40

或者大佬有没有什么情况会 MLE 的分享一下,谢谢。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int n, m, u, v, fir[N], nxt[N << 1], son[N << 1], tot, Q, fa[N][20], dep[N], dfsn[N], sum[N][20], sz[N], b[N], a[N], lca, tem, id[N];
int fir2[N], nxt2[N << 1], son2[N << 1], w2[N << 1], to[N], ans[N], f[N], vis[N], TOT[N], now, ttem, SUM, Sum, now1;
//f[i] : the distance of the nearest ; to[i] : the dot of the nearest ; TOT[i] : sz[i] - sigma(sz[son[i]] , son[i] is ancestors to key dots)
inline void add(int x, int y){
	nxt[++tot] = fir[x];
	fir[x] = tot;
	son[tot] = y;
}
inline void add2(int x, int y, int z){
	nxt2[++tot] = fir2[x];
	fir2[x] = tot;
	son2[tot] = y;
	w2[tot] = z;
}
inline void dfs(int x, int ff){
	sz[x] = 1, dfsn[x] = ++tot, fa[x][0] = ff, dep[x] = dep[ff] + 1;
	for(int i = 1; i <= 19; i++) fa[x][i] = fa[fa[x][i - 1]][i - 1];
	for(int i = fir[x]; i ; i = nxt[i]){
		if(son[i] == ff) continue ;
		dfs(son[i], x);
		sz[x] += sz[son[i]];
	} 
}
inline bool cmp(int x, int y){
	return dfsn[x] < dfsn[y];
}
inline int LCA(int x, int y){
	if(dep[x] > dep[y]) swap(x, y);
	for(int i = 19; ~i; i--){
		if(dep[fa[y][i]] >= dep[x]) y = fa[y][i];
	}
	if(x == y) return x;
	for(int i = 19; ~i; i--){
		if(dep[fa[x][i]] != dep[fa[y][i]]) x = fa[x][i], y = fa[y][i];
	}
	return fa[x][0];
}
inline void init(){
	for(int i = 1; i <= m; i++) fir2[a[i]] = ans[a[i]] = to[a[i]] = TOT[a[i]] = vis[a[i]] = 0, f[a[i]] = 1e9;
	m = tot = 0;
}
inline int LCA_son(int x, int y){
	if(dep[x] > dep[y]) swap(x, y);
	for(int i = 19; ~i; i--){
		if(dep[fa[y][i]] > dep[x]) y = dep[fa[y][i]];
	}
	return y;
}
inline void dp1(int x, int ff){
	TOT[x] = sz[x];
	if(vis[x]) f[x] = 0, to[x] = x;
	for(int i = fir2[x]; i; i = nxt2[i]){
		if(son2[i] == ff) continue ;
		dp1(son2[i], x);
		TOT[x] -= sz[LCA_son(x, son2[i])];
		if(f[son2[i]] + w2[i] < f[x]){
			f[x] = f[son2[i]] + w2[i];
			to[x] = to[son2[i]];
		}
		else if(f[son2[i]] + w2[i] == f[x]){
			to[x] = min(to[x], to[son2[i]]);
		}
	}
}
inline void dp2(int x, int ff){
	for(int i = fir2[x]; i ; i = nxt2[i]){
		if(son2[i] == ff) continue ;
		if(f[x] + w2[i] < f[son2[i]]){
			f[son2[i]] = f[x] + w2[i];
			to[son2[i]] = to[x];
		}
		else if(f[x] + w2[i] == f[son2[i]]){
			to[son2[i]] = min(to[x], to[son2[i]]);
		}
		dp2(son2[i], x);
	}
}
inline void dp(int x, int ff){
	for(int i = fir2[x]; i ; i = nxt2[i]){
		if(son2[i] == ff) continue ;
		now = son2[i], SUM = 0;//SUM : 往上跳的步数
		ttem = w2[i] - (f[x] - f[son2[i]]) - 1;//中间的点只有 w[i] - 1 个
		if(ttem >= 0){
			SUM = ttem / 2 + (f[x] - f[son2[i]]);
			if(ttem & 1) SUM += (to[son2[i]] <= to[x]);
			for(int i = 19; ~i; i--){
				if(SUM >= (1 << i)){
					Sum -= (1 << i);
					now = fa[now][i];
				}
			}
			ans[to[son2[i]]] += sz[now] - sz[son2[i]];
			now1 = LCA_son(x, now);
			ans[to[x]] += sz[now1] - sz[now];	
		}
		else{
			SUM = w2[i] - 1;
			for(int i = 19; ~i; i--){
				if(SUM >= (1 << i)){
					Sum -= (1 << i);
					now = fa[now][i];
				}
			}
			ans[to[son2[i]]] += sz[now] - sz[son2[i]];
		}
		dp(son2[i], x);
	}
}
int main(){
	memset(f, 63, sizeof(f));
	scanf("%d", &n);
	for(int i = 1; i < n; i++){
		scanf("%d%d", &u, &v);
		add(u, v), add(v, u);
	}
	tot = 0;
	dfs(1, 0);
	scanf("%d", &Q);
	while(Q--){
		init();
		scanf("%d", &tem);
		for(int i = 1; i <= tem; i++) scanf("%d", &b[i]), vis[b[i]] = 1, id[i] = b[i];
		sort(b + 1, b + tem + 1, cmp);
		for(int i = 1; i < tem; i++){
			a[++m] = b[i];
			a[++m] = LCA(b[i], b[i + 1]);
		}
		a[++m] = b[tem];
		a[++m] = 1;
		sort(a + 1, a + m + 1, cmp);
		m = unique(a + 1, a + m + 1) - a - 1;
		for(int i = 1; i < m; i++){
			lca = LCA(a[i], a[i + 1]);
			add2(lca, a[i + 1], dep[a[i + 1]] - dep[lca]);
		}
		dp1(1, 0);
		dp2(1, 0);
		for(int i = 1; i <= m; i++) ans[to[a[i]]] += TOT[a[i]];
		dp(1, 0);
		for(int i = 1; i <= tem; i++){
			printf("%d ", ans[id[i]]);
		}
		putchar('\n');
	}
	return 0;
}
/*
10
2 1
3 2
4 3
5 4
6 1
7 3
8 3
9 4
10 1
1
4
8 7 10 3

*/
2023/6/25 13:40
加载中...