K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
假设我们需要统计多条树上路径各自覆盖的节点的总次数,采用树上点差分算法优化时间复杂度,无需每次遍历整条路径。
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)] -= 1
cnt[fa[lca(u,v)]] -= 1
cnt[u] += 1,cnt[v] += 1,cnt[lca(u,v)] -= 2
cnt[lca(u,v)] -= 2
cnt[u] += 1,cnt[v] += 1,cnt[fa[lca(u,v)]] -= 2
cnt[fa[lca(u,v)]] -= 2
cnt[u] += 1,cnt[v] += 1,cnt[lca(u,v)] -= 2,cnt[fa[lca(u,v)]] -= 1