树上差分在竞赛中的应用NOIPCSP-SACM-ICPC

树上差分/NOIP/CSP_S/ACM-ICPC树上差分树上差分的基本操作就是对树上的一段路径或链进行区间查询。如果是针对点权的查询，被称为点差分；如果是对边权的查询，被称为边差分。树上差分就是利用差分的性质，对路径上的重要节点进行修改，而不是暴力全改。通过深度优先搜索遍历求出差分数组的前缀和，可以达到降低复杂度的目的。树上差分可以多次对树的一个路径进行修改，并在最后询问某一节点或区间的结果。修改的时间复杂度是O(1),查询的时间复杂度为O(N)。点差分若将树上两点u,v之间路径上的所有点的点权增加x。令o是点u,v的最近公共祖先，即o=LCA(u,v)。o的父亲节点为p。则差分操作如下：在节点u和节点v的位置增加点权x，即d[u]+=x,d[v]+=x；在节点u和节点v的最近公共祖先o的位置，以及o的父亲节点p，调减点权x，即d[o]-=x,d[p]-=x。这样dfs遍历统计以每个节点为根的子树的子节点权值和，即当前节点的最终权值。这个考虑思路类似于对于一个数列的差分/前缀和的关系。边差分对路径上的边权进行差分的过程叫做树的边差分。由于差分操作只能将权值放在点上，所以习惯上将边的权值存在深度更深（靠下）的节点上。边差分存在子节点中的原因是，因为子节点具有唯一性。 若将树上两点u,v之间路径上的所有边权增加x。如上，令o=LCA(u,v)，以每条边两端深度较大的节点存储该边的差分数组。则操作如下：d[u]+=x,d[v]+=x,d[o]-=2*x。此处和点差分不同。可以理解为d[o]存储的是边(o,p)的权值，其中p为o的父亲节点，这个权值不在点u,v之间的路径上，所以可以一次性调减完成。同样dfs遍历统计以每个节点为根的树的节点的权值和，就是当前节点到父亲节点的边的最终权值。例题：最大流农夫约翰给他的牛棚的N个隔间之间安装了N−1根管道，隔间编号从1到N。所有隔间都被管道连通了。农夫约翰有K条运输牛奶的路线，第i条路线从隔间si运输到隔间ti。一条运输路线会给它的两个端点处的隔间以及中间途径的所有隔间带来一个单位的运输压力。你需要计算压力最大的隔间的压力是多少。第一行输入两个整数N和K。接下来N−1行每行输入两个整数x和y，其中x!=y。表示一根在牛棚x和y之间的管道。接下来K行每行两个整数s和t，描述一条从s到t的运输牛奶的路线。输出一个整数，表示压力最大的隔间的压力是多少。此题可以将n个隔间看作n个节点，节点之间n-1条管道可以理解为n条边。那么显然这是一颗树。为什么是树，请大家翻阅作者其他文章。题意很明显是多次修改(k次)路径si,ti之间的点权，最后查询最大点权的点。这明显是一个树上点差分的板子题。篇幅所限，样例、代码请到作者主页留言讨论。谢谢。例题：松鼠的新家松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n−1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a1，再去a2，……，最后到an，去参观新家。 可是这样会导致重复走很多房间，懒惰的维尼不停地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。维尼是个馋家伙，立马就答应了。现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。松鼠参观指南上的最后一个房间an是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。输入第一行一个正整数n，表示房间个数第二行n个正整数，依次描述a1,a2,⋯,an。n−1行，每行两个正整数x,y，表示标号x和y的两个房间之间有树枝相连。输出一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。如上题，这是一道标准的树上点差分模板题目。依旧是区间修改，区间查询的老套路。区别是松鼠的参观指南就是它修改的路径。即随着参观路径，进行区间修改，最后对树上的所有点进行统计，即答案。篇幅所限，样例、代码请到作者主页留言讨论。谢谢。例题：运输计划公元2044年，人类进入了宇宙纪元。L国有n个星球，还有n−1条双向航道，每条航道建立在两个星球之间。这n−1条航道连通了L国的所有星球。小P掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从ui号星球沿最快的宇航路径飞行到vi号星球去。显然，飞船驶过一条航道是需要时间的，对于航道j，任意飞船驶过它所花费的时间为tj，并且任意两艘飞船之间不会产生任何干扰。为了鼓励科技创新，L国国王同意小P的物流公司参与L国的航道建设，即允许小P把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。在虫洞的建设完成前小P的物流公司就预接了m个运输计划。在虫洞建设完成后，这m个运输计划会同时开始，所有飞船一起出发。当这m个运输计划都完成时，小P的物流公司的阶段性工作就完成了。如果小P可以自由选择将哪一条航道改造成虫洞，试求出小P的物流公司完成阶段性工作所需要的最短时间是多少？输入第一行包括两个正整数n,m（n,m<=2*10^5），表示L国中星球的数量及小P公司预接的运输计划的数量，星球从1到n编号。接下来n−1行描述航道的建设情况，其中第i行包含三个整数ai,bi和ti，表示第i条双向航道修建在ai与bi两个星球之间，任意飞船驶过它所花费的时间为ti。接下来m行描述运输计划的情况，其中第j行包含两个正整数uj和vj，表示第j个运输计划是从uj号星球飞往vj号星球。输出一个整数，表示小P的物流公司完成阶段性工作所需要的最短时间。题目大意与上两题类似，有许多条运输路径，可以被看作一棵树。然后给出一些点对。考虑将某一条边的权值变为0后，求点对间的最大距离最小，并给出最小值。题意中的完成工作，即所有工作的最长时间，即点对间的最大距离或权值。要求完整工作最短时间，即这个值最小。先不考虑树上差分，一般最...最...的求值模型会考虑使用二分答案，特别是在上题的数据量前提下。具体可参见拙著《复杂二分在竞赛中的应用》。此处不赘述。求点对间的距离或权值，一般有三种方法：倍增、树链剖分和Tarjan算法。内容过于复杂，这里不做介绍。二分check()函数中会用到树上差分。设当前二分出来答案为x。以x值为基点观察点对：对于dis[i]<=x的点对可以忽略。对于dis[i]>x的点对，需要统计（设计入变量num）并且删掉路径i上的一条边。接下来考虑删除最长距离路径中的哪条边。显然，如果删掉某条边能使所有点对距离都小于等于x，那么这条边的权值w[i]必然满足大于等于max(dis[i])-x。需要统计满足上条件的边在dis[i]>x的点对路径上的出现次数。这个环节就需要使用树上差分了。对于点对(xi,yi)，设数组p[]记录两点间边出现得次数。如果dis[i]>x，即第i条路径满足条件，则p[xi]++,p[yi]++,p[lca(xi,yi)]–=2。完成第i条路径得区间修改。进一步需要统计第i条路径上点t的数组p[]的前缀和qz[t]。qz[t]就是结点t和其父亲节点所连边出现的次数。如果存在qz[t]>=num，说明找到了要去掉的边。二分check返回真。x值再往大调整。否则说明没有找到，则x往小调整。篇幅所限，样例、代码请到作者主页留言讨论。谢谢。例题：最小割一个具有n个节点和m条边的简单未加权图G。图G是一个既不包含环也不包含重边的无向图。设T是G的生成树。如果G中的一个割只割T的一条边，则说这个割是关于T的。题目要求找到图G关于给定生成树T的最小割。输入包含几个测试用例。第一行是单个整数t（1≤t≤5），即测试用例的数量。接下来是t个测试用例。每个测试用例包含几行。第一行包含两个整数n（2≤n≤20000）和m（n−1≤m≤200000）。下面的n−1行描述了生成树T，每一行都包含对应于一条边的两个整数u和v。接下来的m−n+1行描述无向图G，并且它们中的每一行都包含两个整数u和v，这两个整数对应于不在生成树T中的边。对于每个测试用例，您应该输出关于给定生成树T的图G的最小割。题意求图G的最小割，但是这个割有且仅有生成树T的一条边。对于一棵树，加上一条边，会形成对应的环。如果删掉这个环上的边，那么刚加上的那条边也要删掉。即如果删掉这条树边，所对应的最小边集的数量要加1。那么把n-1条边分配给点的思路就是树剖，但是超时。换一种方法考虑。因为生成树T中只有一条边属于割。那么割对生成树T来说只是分成了两个子树。本题只需要