一、拓扑排序

有多个形如$x_i < x_j$的不等式,求这些不等式是否有解,并求出可能的大小关系。
把不等关系看成有向边,建图,从入度为$0$的所有点开始做一次多源BFS。需要注意的是每次只能将已出队的点移除后入度为$0$的点入队
当图中不存在环时,不等式组有解。反之,不等式组无解。这些点的出队顺序就是可能的大小关系,即图的拓扑序。显然,只有有向无环图才有拓扑序。

题目链接


一、思路解析

给出一棵树,要求按顺序走完给定的所有点,每移动一步就要给这次移动经过的点增加$1$的点权。求每一个点的最小点权。
显然这是一个树上差分的题目,因为树上两点之间有且仅有一条最短路。并且,只有每一步都走最短路,最终的答案才会是最优(树上两点间无论如何走,经过的边组成的边集一定包含最短路上的所有点)。

1、LCA(倍增法)

不知道倍增是个啥的同志们可以先看看这题
$LCA$的倍增求法和$ST$表一样,都是需要先进行一次$O(N\log N)$的预处理。只是求$LCA$的时间复杂度是$O(\log N)$,和$ST$表不同。这也不难理解,$ST$表是在区间(链)上的,而求$LCA$是在树上的,不能通过简单代数加减求得。
倍增求$LCA$有两步预处理,分别是一次$DFS$(弄清楚各个点的父节点以及深度),和一次递推计算(感觉像$DP$一样。)