夏晓光(loveJY)的博客

A

我们肯定可以按照拓扑序删点

然后先删掉有n-1个点链的,再依次删下去

floyed传递闭包,得到连通性

然后我们考虑一个点能被多少点到达,同时能到达多少点

如果这个加起来为n-1,那我一定能确定他的排名,复杂度$O(n^3)$

大于等于最长路小于等于最短路

这个显然可以用点表示前缀和$S_i-c<=S_{j}$

然后就能建出图了!

经典题了

显然我们只要知道每个长为1的区间的奇偶性

那么显然我只要知道r-1和r的奇偶关系

显然一个区间查询可以知道前缀和区间l-1和r的奇偶性

然后我们可以通过奇偶性推导,也就是说一个连通块里的都是可以相互推出的

那么就做完了qwq我们只需要把每条边连接l-1和r,然后最小生成树即可

$sum_0=0$已知,剩下都可以推导出

tarjan求LCA

离线O(n)

维护并查集

回溯的时候我们再把儿子和父亲合并

然后你会发现我们dfs到点x,之后再某一时刻dfs到y的时候,我们一定没有回溯到lca以上的位置

这样我们就可以在并查集里面查询x的祖先是什么即可

也就是说,我们把询问挂在dfn序大的那个点上,然后回溯到那个点,查询另一个点在并查集里的祖先

正确原因就是dfs过程不会回溯到LCA以上的祖先

严格次小生成树

考虑建出最小生成树然后拿非树边去替换

查询路径最小值

这样做的问题是我们得出的可能会因为非树边和最小树边相等而错掉

所以我们还要记录一个最小的

做法一

二分答案,然后会发现我们要把那些大于mid的都搞掉

会发现把他们交集的最大边干掉即可

做法二

上述过程不需要二分

我们一定要改最大链,然后再在最大链和次大链改最大的....

直到所有的都被判断一次,其中一个一定是ans

即$min(max(len[1]-mx[k+1],len[k]))$

树链判交

一定要有一个lca在另一个链上

而一个点在链上的充分条件就是要有一个端点做lca等于他,另一个端点做lca等于他

树链求交

(u,v),(x,y)

$lca(u,x),lca(u,y),lca(v,x),lca(v,y)$

四个点中dfn序最大的两个就是新链两个端点

为啥呢?我也不太懂

正确的前提是树链判交成立

拓扑排序计数

显然...

拓扑图最小链覆盖等于最长反链

最长反链：最大的点集，点集中任意两个点无法互相到达

向右下一堆链变成向左上最长链

然后这个东西相当于最长左上链可以动态规划

鬼知道为什么这么小

做法还是很妙的

首先我们建立源汇点然后最长路径等于s->t的最长路-2

从sbfs一遍得到f,从tbfs一遍得到z

然后你会发现我们枚举一个点断开的过程可以维护

就是考虑按照拓扑序断开点,然后左边划分给拓扑序小于x的集合,右边维护拓扑序大于他的集合

那么整体的答案就是左边集合与右边集合右边的一个点$f_x+g_z-1$

实现的时候,我们断掉这个点分入右边可以用枚举出边然后把每个$pair$用堆删除

然后我们同时可能会加入一些新的贡献(就是点x和右边集合的)

这个也可以堆

二分图最大匹配=二分图最小点覆盖