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

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

A

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

B

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

C

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

D

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

程序运行统计
暂无判题统计
提交0次 正确率0.00%
答案解析