K12教育赛事综合服务平台
聚乐之家官方网站
下载聚乐之家官方App
专注青少年竞赛题库网站
假设diff数组初始全为0，fa[x]表示节点x的父节点，lca(u,v)表示u和v的最近公共祖先，后续通过一次后序遍历累加子树和即可得到每个节点的最终权值增量。
diff[u] += 1，diff[v] += 1，diff[lca(u,v)] -= 1，diff[fa[lca(u,v)]] -= 1
diff[u] += 1
diff[v] += 1
diff[lca(u,v)] -= 1
diff[fa[lca(u,v)]] -= 1
diff[u] += 1，diff[v] += 1，diff[lca(u,v)] -= 2
diff[lca(u,v)] -= 2
diff[u] += 1，diff[v] += 1，diff[fa[lca(u,v)]] -= 2
diff[fa[lca(u,v)]] -= 2
diff[u] += 1，diff[v] -= 1，diff[lca(u,v)] += 1，diff[fa[lca(u,v)]] -= 1
diff[v] -= 1
diff[lca(u,v)] += 1