故事是这样的，辣鸡我被要求写dfs序，前置技能是树上差分，然后只好十分不情愿地学习了一下。

---

 

差分

差分数组(b)：原数组(a)中相邻的差构成的数组。(b[i]=a[i]-a[i-1]，b[1]=a[1])

性质：其前缀和为原数组。(b[2]=a[2]-a[1]，b[3]=a[3]-a[2]，b[i]=a[i]-a[i-1]，b[1]+b[2]+...b[i]=a[i])

Skill：根据差分数组(c)求前缀和数组。

c[i]=∑(1<=j<=i)a[j]=∑(1<=j<=i)∑(1<=k<=j)b[k]=∑(1<=j<=i)(j-i+1)*b[j]=(i+1)*∑(1<=j<=i)b[j]-∑(1<=j<=i)j*b[j]；

　　用途：树状数组的区间修改操作。

类似地，经常用差分来维护序列的区间操作或者记录区间的贡献。

树上差分

 处理的数据有关于边(x,y)：

　　b[x]++,b[y]++,b[lca(x,y)]-=2.

（lca没有边信息要存，所以全减掉）

处理的数据有关于点(x,y)：

　　b[x]++,b[y]++,b[lca(x,y)]--,b[father[lca(x,y)]]--.

 （lca信息也属于这条链内，所以只减一次）