社区讨论

无法理解的RE错误求助

学术版参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mm0n6dkr
此快照首次捕获于
2026/02/24 21:29
2 周前
此快照最后确认于
2026/02/26 12:30
2 周前
查看原帖
我写了一个长链剖分代码,通过了样例,交上去大部分测试点获得 RE,测试点 1 和 6 可以通过。
代码如下:
CPP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
typedef long long LL;

const int MAX_N = 300000+10;

int n, q, lian[MAX_N], dep[MAX_N], fa[MAX_N], hson[MAX_N], htop[MAX_N], siz[MAX_N];
vector<int> e[MAX_N];
vector<LL> g[MAX_N];

void dfs_fir (int u, int fff) {
	fa[u] = fff;
	dep[u] = dep[fff] + 1;
	hson[u] = 0;
	siz[u] = 1;
	for(auto v : e[u]) {
		if(v == fff) continue;
		dfs_fir(v, u);
		siz[u] += siz[v];
		if(hson[u] == 0 || dep[v] > dep[hson[u]]) hson[u] = v;
	}
}

void dfs_sec (int u, int t) {
	htop[u] = t;
	++ lian[t];
	if(hson[u] > 0) {
		dfs_sec(hson[u], t);
		for(auto v : e[u]) {
			if(v == fa[u] || v == hson[u]) continue;
			dfs_sec(v, v);
		}
	}
	if(u == t) {
		g[u].resize(lian[u]);
	}
}

void dp (int u) {
	if(hson[u] == 0) {
		g[htop[u]][dep[u]-dep[htop[u]]] = 0;
	}
	else {
		dp(hson[u]);
		for(auto v : e[u]) {
			if(v == fa[u] || v == hson[u]) continue;
			dp(v);
			for(int i = 0; i < lian[v]; i ++) {
				g[htop[u]][dep[u]-dep[htop[u]]+1+i] += g[v][i];
			}
		}
	}
	if(u == htop[u]) {
		int now = u;
		for(int i = 0; i < lian[u]; i ++) {
			if(now <= 0 || now > n) exit(0);
			g[u][i] += siz[now] - 1;
			now = hson[now];
		}
	}
}

int main () {
	scanf("%d%d",&n,&q);
	for(int i = 1; i <= n-1; i ++) {
		int x, y;
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs_fir(1, 0);
	dfs_sec(1, 1);
	dp(1);
	for(int i = 1; i <= n; i ++) {
		for(int j = 1; j < lian[i]; j ++) {
			g[i][j] += g[i][j-1];
		}
	}
	while(q --) {
		int p, k;
		scanf("%d%d",&p,&k);
		LL ans = (siz[p] - 1) * min(k, dep[p] - 1);
		if(k > lian[htop[p]] - dep[p] + dep[htop[p]] - 1) 
			k = lian[htop[p]] - dep[p] + dep[htop[p]] - 1;
		if(k < 0) printf("%lld\n",ans);
		else {
			ans += g[htop[p]][dep[p]-dep[htop[p]]+k] - g[htop[p]][dep[p]-dep[htop[p]]];
			printf("%lld\n",ans);
		}
	}
	return 0;
}
经过排查,在 dp 函数中
CPP
	if(u == htop[u]) {
		int now = u;
		for(int i = 0; i < lian[u]; i ++) {
			if(now <= 0 || now > n) exit(0);
			g[u][i] += siz[now] - 1;
			now = hson[now];
		}
	}
}
这个部分出现了错误。
当我将所有关于变量 now 的代码删去后,程序不再 RE,我本以为问题出现在 now 变量上,我检查了 now 变量的取值,在程序运行过程中始终在 0n0\sim n 中,没有出现问题。
CPP
if(u == htop[u]) {
		int now = u;
		//if(now < 0 || now > n) exit(0);
		for(int i = 0; i < lian[u]; i ++) {
			//if(now < 0 || now > n) exit(0);
			g[u][i] += siz[now] - 1;
			if(i < lian[u] - 1) now = hson[now];
			//if(now < 0 || now > n) exit(0);
		}
	}
之后我又注释掉 now 变量并对 g[u][i] 进行越界检查,即改为 g[u].at(i) 也并没有问题。
想问一下这个地方哪里出了问题?
谢谢。OVO

回复

7 条回复,欢迎继续交流。

正在加载回复...