「咕咕网校 - 基础省选」树上问题的进阶 by Drench

一定要在noip之前把自己花钱买的Luogu网课梳理完！QAQ

树上前缀和：

对于有根树，在每个点记录 val （点权） 和 sum（到根的点权之和）

当然记录的值因题而异（但是既然叫树上前缀和当然就要这么定义啊）

就可以做一些奇奇怪怪的操作了。

还是看题来理解这玩意儿的妙用吧2333

EG1

给定树和各点点权，t次询问，每次求u到v路径上的点权和。（1e5）

是道板子题了。

从根开始dfs，到每个点时记录该点的val和sum

其中sum为该点到祖先路径上点权之和，包括自己。

每次输出sum[u]+sum[v]-2*sum[lca(u,v)]+val[lca(u,v)]。

EG2

给定初始点权为0的树，n次操作，每次对u,v路径上每点+x。
求最后每点点权。（1e5）

运用差分思想。

对每个点记录一个val值，初始为0。

对于每次操作：

这样，每个点的真实点权就是该点的子树点权和。

val[u]+=x;
val[v]+=x;
val[lca(u,v)]-=x;
if(fa[lca(u,v)]!=lca[u,v])
fa[lca(u,v)]-=x;

实现O(4)修改，最后用O(n)得到答案。

“经典的树上差分。”——ddd

 EG3

给定树，边有边权。
求有多少对（u,v）使u,v路上所有边的边权异或和为0（1e5）
其中异或和=所有数异或起来的结果

 记sum[x]为x到祖先的异或和。

由于异或有：

a xor a = 0

所以如下图，在sum[u] xor sum[v]时，lca以上的屎色线已经被消掉了。

所以ans=sum[u] xor sum[v]

问题转化为：有1e5个数（sum），求中间有多少对数异或和=0

也就是有多少对相等的数。

用一个map记录，然后遍历map就行了。

————————————

to be continued

「咕咕网校 - 基础省选」树上问题的进阶 by Drench

原文：https://www.cnblogs.com/qwerta/p/9600669.html