前言
题目链接：Hydro & bzoj；黑暗爆炸；洛谷。
题意简述
DAG 求删点后最长路的最小值。
\(n \leq 5 \times 10 ^ 5\)，\(m \leq 10^6\)。
题目分析
其实对于删点 / 边加查询最长 / 短路的套路是有的。比如：故乡的梦、桥。本题也类似。
我们考虑，如果删除的边不在原来最长路上，那么删之后的图的最长路不变。又因为我们一定可以删除最长路上的一条边来得到不劣的答案，所以，我们删除就只会删除原来最长路上的某一个点。如果最长路不唯一，任取不影响正确性。
考虑最长路 \(d_1 \ldots d_k\)，设删除的点为 \(u = d_{p}\)。那么删除后的最长路可能是 \(d_1 \ldots d_{p - 1}\) 或 \(d_{p + 1} \ldots d_k\)，也可能是其他不经过点 \(u\) 的最长路。这么看似乎没什么头绪，我们稍微转化一下。对于原图的任意最长路，其起点入度和终点出度必为 \(0\)，所以套路地，我们用一个超级源点 \(S\) 连向所有入度为 \(0\) 的点，所有出度为 \(0\) 的点连向超级汇点 \(T\)。这样，我们发现最长路 \(d_1 = S\)，\(d_k = T\)。以及，删点后的最长路一定形如：\(S \rightarrow d_{i} \rightarrow x \rightarrow y \rightarrow d_{j} \rightarrow T\)，其中 \(i \lt p\) 并且 \(j \gt p\)。那么 \(d_i\) 就是以 \(S\) 为根的最长路径树上，\(x\) 到链 \(S \sim T\) 的结点，\(d_j\) 是以 \(T\) 为根的反图的最长路径树上， \(y\) 到链 \(S \sim T\) 的结点。这是由于，我们需要使得 \(S \rightarrow x\) 和 \(y \rightarrow T\) 是最长路。
用 BFS 或 DFS 什么的标记一下预处理很方便。不妨把 \((x, y)\) 这条非树边挂在 \(d_i\) 上，记作二元组 \(v_i = (d_j, len)\)，其中 \(len\) 是经过 \((x, y)\) 最长路长度。查询变成了在 \(v_{1 \sim p - 1}\) 中，前者 \(\gt p\) 的后者的最小值。
按照 \(p = 1 \ldots k\) 的顺序扫过去，对于一个 \(d_i = p\) 的二元组，在一个数据结构的 \(d_j\) 位置取 \(\max \{ len \}\)。对于 \(p \in [2, k - 1]\)，我们查询删除这个点的答案，就是在 \(i - 1\) 操作后的基础上查询 \(i + 1 \sim k\) 的最大值。树状数组维护即可。
时间复杂度：\(\Theta((n + m) \log n)\)，瓶颈在于树状数组单点修改，后缀查最值。
代码
#include <cstdio>
#include <iostream>
using namespace std;
constexpr const int MAX = 1 << 27, yzh_i_love_you = 1314520736;
char buf[MAX], *p = buf;
#define getchar() (*p++)
#define isdigit(x) ('0' <= x && x <= '9')
inline void read(int &x) {
x = 0; char c = 0;
for (;!isdigit(c); c = getchar());
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
}
const int N = 500010;
const int M = 1000010;
int n, m;
int line[N], whr[N], tim;
bool inpath[M];
struct Graph {
struct node {
int to, nxt;
} edge[M + N * 2];
int head[N], du[N], tot;
inline void add(int u, int v) {
edge[++tot] = {v, head[u]};
head[u] = tot, ++du[v];
}
inline node & operator [] (int x) {
return edge[x];
}
int dis[N], fr[N], bl[N];
inline void solve(int root) {
static int Q[N], top(0);
Q[++top] = root, dis[root] = -1;
while (top) {
int now = Q[top--];
for (int i = head[now]; i; i = edge[i].nxt) {
int to = edge[i].to;
if (dis[now] + 1 >= dis[to]) {
dis[to] = dis[now] + 1;
fr[to] = i;
}
if (!--du[to]) Q[++top] = to;
}
}
}
void mark(int s) {
static int Q[N], top(0);
Q[++top] = s;
bl[s] = s;
while (top) {
int now = Q[top--];
for (int i = head[now]; i; i = edge[i].nxt) {
int to = edge[i].to;
if (fr[to] != i) continue;
bl[to] = inpath[i] ? to : bl[now];
Q[++top] = to;
}
}
}
} xym, yzh;
struct Trans {
struct node {
int to, len, nxt;
} edge[M];
int tot, head[N];
inline void add(int u, int v, int w) {
edge[++tot] = {v, w, head[u]};
head[u] = tot;
}
inline node & operator [] (int x) {
return edge[x];
}
} trans;
void getpath() {
int T = 1, S;
for (int i = 1; i <= n; ++i) if (xym.dis[i] > xym.dis[T]) T = i;
for (S = T; xym.fr[S]; S = yzh[xym.fr[S]].to);
for (int i = S; ; i = xym[yzh.fr[i]].to) {
line[++tim] = i;
whr[i] = tim;
if (!yzh.fr[i]) break;
inpath[yzh.fr[i]] = true;
}
}
struct Bit_Tree {
int tree[N];
inline int lowbit(int x) {
return x & -x;
}
inline void modify(int p, int v) {
for (int i = p; i; i -= lowbit(i)) tree[i] = max(tree[i], v);
}
inline int query(int p) {
int res = 0;
for (int i = p; i <= tim; i += lowbit(i)) res = max(res, tree[i]);
return res;
}
} tree;
signed main() {
fread(buf, 1, MAX, stdin);
read(n), read(m);
for (int i = 1, u, v; i <= m; ++i) {
read(u), read(v);
xym.add(u, v);
yzh.add(v, u);
}
for (int i = 1; i <= n; ++i) {
if (!xym.du[i]) xym.add(0, i), yzh.add(i, 0);
if (!yzh.du[i]) xym.add(i, n + 1), yzh.add(n + 1, i);
}
xym.solve(0), yzh.solve(n + 1);
getpath();
xym.mark(0), yzh.mark(n + 1);
for (int u = 1; u <= n; ++u)
for (int i = xym.head[u]; i; i = xym[i].nxt) {
int v = xym[i].to;
if (xym.fr[v] == i) continue;
if (whr[xym.bl[u]] + 1 >= whr[yzh.bl[v]]) continue;
trans.add(whr[xym.bl[u]], whr[yzh.bl[v]], xym.dis[u] + 1 + yzh.dis[v]);
}
int ans = 0x3f3f3f3f, u = -1;
for (int i = 1; i <= tim - 1; ++i) {
if (i >= 2) {
int res = tree.query(i + 1);
res = max(res, xym.dis[line[i - 1]]);
res = max(res, yzh.dis[line[i + 1]]);
if (res < ans) ans = res, u = line[i];
}
for (int j = trans.head[i]; j; j = trans[j].nxt)
tree.modify(trans[j].to, trans[j].len);
}
printf("%d %d", u, ans);
return 0;
}