Problem
给一个\(n\)个点，\(m\)条边的DAG，找到一个点，使得删去这个点后的最长路径最短。
\(2 \le n \le 500000,1 \le m \le 1000000\)。
Solution
看到DAG就想到拓扑。
求出以\(x\)为起点的最长路径长度\(ds_x\)和以\(x\)为终点的最长路径长度\(dt_x\)。可以通过跑正反图拓扑实现。
设第\(x\)个点的拓扑序为\(TX_x\)。
对于一条边\(u \to v\)，经过它的最长路径长度为\(dt_u + ds_v + 1\)，正确性显然。
考虑枚举删的点，假设我们现在删除\(x\)，我们假设所有\(TX_i < TX_x\)的点放在集合\(A\)，\(TX_i > TX_x\)的放在集合\(B\)，\(x\)在中间。
此时的最长路径分三种：\(A\to A,A \to B,B\to B\)。
- \(A\to A\)：\(\max_{i \in A} \{dt_i\}\)
- \(A \to B\)：\(\max_{(u,v) \in E,u \in A,v \in B} \{dt_u +ds_v + 1 \}\)
- \(B \to B\)：\(\max_{i \in B} \{ds_i\}\)
\(x\)原来在\(B\)集合，现在不在\(B\)集合，则删除\(ds_x\)。
\(x\)在反图中连接的点都存在第二种情况，删除。
下一次删除前，\(x\)在\(A\)集合，则加入\(dt_x\)。
\(x\)在图中连接的点都存在第二种情况，加入。
发现需要维护一个支持删除加入，求最值的东西，那么可以使用平衡树权值线段树。（其实multiset应该可以，但是我不会用）
# include<bits/stdc++.h>
using namespace std;
const int N = 500005,M = 1000005;
int n,m;
vector <int> g[N],g2[N];
int ds[N],dt[N];
int du[N],du2[N];
int Tx[N],Txtot = 0;
int q[N];
void topsort(void) //dt
{
queue <int> q;
for(int i = 1; i <= n; i++)
{
if(du[i] == 0)
{
q.push(i);
Tx[i] = ++Txtot;
}
}
while(!q.empty())
{
int x = q.front(); q.pop();
for(int i = 0; i < (int)g[x].size(); i++)
{
int v = g[x][i];
dt[v] = max(dt[v],dt[x] + 1);
if(--du[v] == 0) q.push(v),Tx[v] = ++Txtot;
}
}
return;
}
void topsort2(void)
{
queue <int> q;
for(int i = 1; i <= n; i++)
{
if(du2[i] == 0)
{
q.push(i);
}
}
while(!q.empty())
{
int x = q.front(); q.pop();
for(int i = 0; i < g2[x].size(); i++)
{
int v = g2[x][i];
ds[v] = max(ds[v],ds[x] + 1);
if(--du2[v] == 0) q.push(v);
}
}
return;
}
bool compare(const int &x,const int &y)
{
return Tx[x] < Tx[y];
}
struct node
{
int val,l,r;
}T[N << 2];
int tot = 1;
void build(int root,int l,int r)
{
if(l == r) {T[root].val = 0,T[root].l = T[root].r = 0; return;}
int mid = (l + r) >> 1;
T[root].l = ++tot,T[root].r = ++tot;
build(T[root].l,l,mid),build(T[root].r,mid + 1,r);
return;
}
void update(int root,int l,int r,int x,int d)
{
if(l == r && l == x)
{
T[root].val += d;
return;
}
int mid = (l + r) >> 1;
if(l <= x && x <= mid) update(T[root].l,l,mid,x,d);
else if(x > mid) update(T[root].r,mid + 1,r,x,d);
T[root].val = T[T[root].l].val + T[T[root].r].val;
return;
}
int query(int root,int l,int r)
{
if(l == r) return l;
int mid = (l + r) >> 1;
if(T[T[root].r].val > 0) return query(T[root].r,mid + 1,r);
else return query(T[root].l,l,mid);
}
int main(void)
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i++)
{
int a,b; scanf("%d%d",&a,&b);
g[a].push_back(b),g2[b].push_back(a);
++du[b],++du2[a];
}
topsort(),topsort2();
build(1,1,2 * n);
for(int i = 1; i <= n; i++)
{
update(1,1,2 * n,ds[i],1); q[i] = i;
}
sort(q + 1, q + n + 1, compare);
int ans = 1e9 + 7,id = 0;
for(int i = 1; i <= n; i++) // delete i
{
update(1,1,2 * n,ds[q[i]],-1);
for(int j = 0; j < (int)g2[q[i]].size(); j++)
{
int v = g2[q[i]][j];
update(1,1,2 * n,dt[v] + 1 + ds[q[i]],-1);
}
// printf("i = %d,max = %d\n",i,Max);
int Max = query(1,1,2 * n);
// printf("i = %d,Max = %d\n",i,Max);
if(Max < ans)
{
ans = Max,id = q[i];
}
// S.insert(dt[i]);
update(1,1,2 * n,dt[q[i]],1);
for(int j = 0; j < (int)g[q[i]].size(); j++)
{
int v = g[q[i]][j];
update(1,1,2 * n,dt[q[i]] + 1 + ds[v],1);
}
}
printf("%d %d\n",id,ans);
return 0;
}