社区讨论
无法理解的RE错误求助
学术版参与者 4已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mm0n6dkr
- 此快照首次捕获于
- 2026/02/24 21:29 2 周前
- 此快照最后确认于
- 2026/02/26 12:30 2 周前
相关题目:P3899 [湖南集训] 更为厉害。
我写了一个长链剖分代码,通过了样例,交上去大部分测试点获得 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;
}
经过排查,在
CPPdp 函数中 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];
}
}
}
这个部分出现了错误。
当我将所有关于变量
CPPnow 的代码删去后,程序不再 RE,我本以为问题出现在 now 变量上,我检查了 now 变量的取值,在程序运行过程中始终在 中,没有出现问题。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 条回复,欢迎继续交流。
正在加载回复...