文章目录 差分树上差分p3128LQB14I砍树题目解题步骤代码样例 差分 差分数组求法： 设原始数组是arr，差分数组是b b[0] = arr[0];b[i] = arr[i] - arr[i-1]; 如果我们要对图中2-4区间的数每个都加上3，就可以在差分数组2的位置加上3，在差分数组4的后一个元素即5的位置减去一个3（目的是消除3对后面区间的影响），再对差分数组前

FJ 给他的牛棚的 N 个隔间之间安装了 N−1 根管道，隔间编号从 1 到 N。所有隔间都被管道连通了。 FJ 有 K 条运输牛奶的路线，第 i 条路线从隔间 si​ 运输到隔间 ti​。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力，你需要计算压力最大的隔间的压力是多少。 第一行输入两个整数 N 和 K。 接下来 N−1 行每行输入两个整数 x 和 y，

Portal. 树上差分。 这里要用的是边差分。 对于一条路径 s → t s\rightarrow t s→t，我们把 s s , s t s_s,s_t ss​,st​ 加一，代表到 s , t s,t s,t 的路径上的隔间压力都加 1 1 1。 注意到 LCA 被重复累加，所以要减 1 1 1。又因为 LCA 的 s lca s_{\text{lca}} slca​ 会