3.LCA的综合运用
（1）树上差分
在序列中，我们定义其前缀和与差分序列，把区间的增减转化为左端点加1，右端点减1，根绝差分序列的前缀和是原序列这一原理，在树上也可以进行类似的简化，其中“区间操作”对应“路径操作”，“前缀和”对应“子树和”
经典模型：给定一张无向图和一棵生成树，求每条“树边”被“非树边”覆盖了多少次
解决方案：树上差分，给树上每一个节点一个初始为0的权值，然后对每条非树边（x,y），令x权值加1，y权值加1，lca(x,y)的权值减2，最后对这棵生成树进行一次dfs，求出f[x]表示以x为根的子树中各节点的权值之和。f[x]就是x与它的父节点之间的“树边”被覆盖的次数
利用树上差分快速求出树上一点在几条给定路径上的模板：[USACO15DEC]Max Flow P
下面我们利用这个模板题所学到的树上差分技巧，分析 noip中是如何运用的呢？
t1.[NOIP2015 提高组] 运输计划 【lca+树上差分+二分答案】
题意：在一棵带权的树上有m条路径，清零一条边的边权使得m条路径的最大值最小
分析：
（1）最长路径最短--->二分--->二分这个最长路径最小值,统计长度>=mid的路径能否在删边后满足长度小于等于mid （求解转判定）
（2）删什么边？--->思考：对于现有的所有长度>=mid的路径，都是不合法的，都需要删边处理
--->得出结论：被所有长度>=mid的路径经过且长度尽量长的边
（3）具体如何统计经过次数？---树上差分！