Luogu3573 [POI2014] RAJ-Rally

题意：给出一个 DAG，边权均为 。

找出一个点，使得删掉这个点后剩余的图中的最长路最短。

，，时限 。

---

不定源最长路不便处理，新建超级源超级汇，分别和所有点连边。问题转化成求超级源到超级汇的最长路。

先将这张图拓扑排序。

考虑若删除点 ，哪些路径不会受到影响。

若路径中有一条边 满足 在拓扑排序中分别位于 的两侧，那么这条路径不会受到影响。

那么，考虑每条边 的贡献。

当删除 内的某个点时，所有包含 的路径都可选。

那么记源到 的最长路为 ， 到汇的最长路为 。

这可以在正反图上两次拓扑求出。

包含 的最长路为 。

这能向区间 贡献答案，问题变成区间取 。容易用可删堆+扫描解决。

复杂度 。