Rally

P3573 [POI2014] RAJ-Rally 题意 给一张 \(DAG\)，问删去一个点的最长路是多少。 题解 好妙的题。 考虑对于每个点求出删除此点之后的最长路。 考虑到一个 \(DAG\) 只会由拓扑序低的点走向高的点。 所以我们按照拓扑序枚举点删除之后的最短路。 考虑根据当前点的拓扑序将 ......

整体二分板题 首先瑞平翻译。 考虑整体二分，用分治函数 solve(l,r,L,R) 解决答案在 \([L,R]\) 之间的边。每次我们加入所有 \([1,MID]\) 之间的边，查询这时的询问是否满足要求，进行整体二分即可。 由于多次加入边比较麻烦，我们用可撤销并查集维护。 时间复杂度 \(O(n ......

可以看做一道比较套路的的 $kruskal$ 重构树。 但或许也是一道复习与入门的好题。 ### 思路 考虑把图论问题转化为树上问题。 发现所求的为路径上最大的最小。 容易想到 $kruskal$ 重构树。 发现由于从两端一起走，不能直接处理。 那么就可以在外面套一个二分，内部直接倍增处理即可。 # ......

网瘾犯了。 https://www.luogu.com.cn/problem/P3573 题意：在 DAG 上删除一点，使得剩下点的最长路最短。 解答：用 $f_v$ 和 $h_v$ 表示终点为 $v$、起点为 $v$ 的单源最长路。按照拓扑序（这样才是 DAG，有 dp 性质）枚举 $u$，每次先 ......

非常好题目，爱来自 xc。 看到有向无环图，想到拓扑序。通过拓扑序，可以轻松求出以每个点为起点的最长路 $disS$与每个点为终点的最长路 $disF$。 如何求总共的最长路？在 $disS,disF,disS_u + 1 + disF_v((u,v)\in E)$ 中取最大值即可。注意最后一项，表 ......

D - Stamp Rally (atcoder.jp) 这题做法很多，我写的是可持久化并查集做法，但是裸的可持久化并查集是 $O(nlog^3n)$，能过但是很慢！看洛谷的题解有一位大佬写了一个很妙的并查集的写法，按秩合并，每一步合并时用vector记录一下这个被合并到的节点的size和当前的时间 ......