若使用点差分统计树上u到v的路径覆盖的所有点的被访问次数，下列操作序列正确的是（设fa[x]表示x的父节点，lca(u,v)表示u和v的最近公共祖先，cnt为差分数组）？

fi494860 单选题共个子题

假设我们需要统计多条树上路径各自覆盖的节点的总次数，采用树上点差分算法优化时间复杂度，无需每次遍历整条路径。

cnt[u] += 1，cnt[v] += 1，cnt[lca(u,v)] -= 1，cnt[fa[lca(u,v)]] -= 1

cnt[u] += 1，cnt[v] += 1，cnt[lca(u,v)] -= 2

cnt[u] += 1，cnt[v] += 1，cnt[fa[lca(u,v)]] -= 2

cnt[u] += 1，cnt[v] += 1，cnt[lca(u,v)] -= 2，cnt[fa[lca(u,v)]] -= 1

正在加载题目数据…

第空

已答 /

子题

第空

提示

该题型需在试卷/作业中作答，单题练习暂不支持

答案解析