社区讨论
萌新疑问
学术版参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @miej2qn5
- 此快照首次捕获于
- 2025/11/25 20:04 3 个月前
- 此快照最后确认于
- 2025/11/25 20:12 3 个月前
下面是树上祖先倍增表的预处理，为什么要在处理完子节点后再倍增是对的，一开始倍增反而不对?
正确：
CPPvoid dfs(int u)
{
top[u] = rt;
tot[u] += tot[f[u][0]] + v[u]; // 记录原树贡献值
for (struct Node* tmp=p[u].nxt;tmp!=NULL;tmp=tmp->nxt) dfs(tmp->to); /// dfs
if (p[u].nxt == NULL) {q.push(u);rea[u] = tot[u];} // 记录当前贡献值 将叶子节点入队
for (int i=1;i<21;i++) f[u][i] = f[f[u][i-1]][i-1]; // 找爸爸
return ;
}
错误:
CPPvoid dfs(int u)
{
top[u] = rt;
tot[u] += tot[f[u][0]] + v[u]; // 记录原树贡献值
for (int i=1;i<21;i++) f[u][i] = f[f[u][i-1]][i-1]; // 找爸爸
for (struct Node* tmp=p[u].nxt;tmp!=NULL;tmp=tmp->nxt) dfs(tmp->to); /// dfs
if (p[u].nxt == NULL) {q.push(u);rea[u] = tot[u];} // 记录当前贡献值 将叶子节点入队
return ;
}
回复
共 1 条回复，欢迎继续交流。
正在加载回复...