树上差分
在讲树上差分之前，首先需要知道树的以下两个性质：
（1）任意两个节点之间有且只有一条路径。
（2）根节点确定时，一个节点只有一个父亲节点
这两个性质都很容易证明。那么我们知道，如果假设我们要考虑的是从u">u到v">v的路径，u">u与v">v的lca">lca是a">a，那么很明显，如果路径中有一点u′">u′已经被访问了，且u′">u′≠a">a，那么uu">'的父亲也一定会被访问，这是根据以上性质可以推出的。
u">v">u">v">lca">a">u′">u′">a">u">所以，我们可以将路径拆分成两条链，u">u->a">a和a">a->v">v。那么树上差分有两种常见形式：（1）关于边的差分；（2）关于节点的差分。
①关于边的差分：
将边拆成两条链之后，我们便可以像差分一样来找到路径了。用cf[i]">cf[i]代表从i">i到i">i的父亲这一条路径经过的次数。因为关于边的差分，a">a是不在其中的，所以考虑链u">u->a">a，
cf[i]">i">i">a">u">a">则就要使cf[u]++">cf[u]++，cf[a]−−">cf[a]??。然后链a">a->v">v，也是cf[v]++">cf[v]++，cf[a]−−">cf[a]??。所以合起来便是cf[u]++">cf[u]++，cf[v]++">cf[v]++，cf[a]−=2">cf[a]?=2。然后，从根节点，对于每一个节点x">x，都有如下的步骤：
（1）枚举x">x的所有子节点u">u
（2）dfs">dfs所有子节点u">u
（3）cf[x]+=cf[u]">cf[x]+=cf[u]
那么，为什么能够保证这样所有的边都能够遍历到呢？因为我们刚刚已经说了，如果路径中有一点u′">u′u′已经被访问了，且u′">u′≠a">a，那么u′">u′的父亲也一定会被访问。所以u′">u′被访问几次，它的父亲也就因为u′">u′被访问了几次。
u′">u′">a">u′">u′">u′">所以就能够找出所有被访问的边与访问的次数了。路径求交等一系列问题就是通过这个来解决的。因为每个点都只会遍历一次，所以其时间复杂度为Θ(n)">Θ(n).
②关于点的差分：
还是与和边的差分一样，对于所要求的路径，拆分成两条链。步骤也和上面一样，但是也有一些不同，因为关于点，u">u与v">v的lca">lca是需要包括进去的，所以要把lca">lca包括在某一条链中，用cf[i]">cf[i]表示i">i被访问的次数。
u">v">lca">lca">cf[i]">i">最后对cf">cfcf数组的操作便是cf[u]++">cf[u]++，cf[v]++">cf[v]++，cf[a]−−">cf[a]??，cf[father[a]]−−">cf[fa[a]]??。其时间复杂度也是一样的Θ(n)">Θ(n).
我们把路径拆成u->a,a->u
每一部分从下向上走
对于u->a部分，只需cf[u]++,cf[a]--
对于a->v部分，只需cf[v]++,cf[a]--
然后发现a被修改了两次，所以我们要对a取消一次重复的差分标记
cf[fa]++,cf[fa[a]]??