$n leq 5e5,m leq 3e6$的DAG，问删掉某个点的最长路最短是多少，并输出这个点。
采用“整体去部分”的思想。先建一源一汇，源连所有点，所有点连汇。$f_i$--从$s$到$i$的最短路；$h_i$--从$i$到$t$的最短路，这俩数组拓扑一下可以算出。一条边对答案有$f_u+1+g_v$的贡献。
假设一开始所有点都在汇，然后按拓扑序逐渐加入源来看最优答案。因为一开始点都在汇，所以只把$h_i$加进数据结构中。然后一个点删除之时，拓扑序在他后面的点与他组成的路径只考虑了最长的那条$g_i$，删之，然后把指向他的边的贡献删掉，如此经过他的路径不会出现在数据结构中，可以提取答案。接着将其加入源。在源部分的经过$i$的路径只有$f_i$是有用的，加之；源汇交接处，$i$的所有出边是有用的，把他们装进数据结构。
由于边权范围是n，所以可以开个桶来配合优先队列删除，而不必写线段树。
1 //#include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 //#include<time.h> 5 //#include<complex> 6 //#include<set> 7 #include<queue> 8 //#include<vector> 9 #include<algorithm> 10 #include<stdlib.h> 11 using namespace std; 12 13 #define LL long long 14 int qread() 15 { 16 char c; int s=0,f=1; while ((c=getchar())<'0' || c>'9') (c=='-') && (f=-1); 17 do s=s*10+c-'0'; while ((c=getchar())>='0' && c<='9'); return s*f; 18 } 19 20 //Pay attention to '-' , LL and double of qread!!!! 21 22 int n,m,s,t; 23 #define maxn 500011 24 #define maxm 3000011 25 26 struct Edge{int to,next;}; 27 struct Graph 28 { 29 Edge edge[maxm]; int first[maxn],le; 30 Graph() {le=2; memset(first,0,sizeof(first));} 31 void in(int x,int y) {Edge &e=edge[le]; e.to=y; e.next=first[x]; first[x]=le++;} 32 }g,g2; 33 34 priority_queue<int> q; 35 int vis[maxn+3]; 36 void Insert(int v) 37 { 38 if (vis[v]) vis[v]--; 39 else q.push(v); 40 } 41 void Delete(int v) {vis[v]++;} 42 43 int que[maxn],head=1,tail=1,du[maxn]; 44 void topo() 45 { 46 for (int i=1;i<=n;i++) 47 for (int j=g.first[i];j;j=g.edge[j].next) 48 { 49 Edge &e=g.edge[j]; 50 du[e.to]++; 51 } 52 for (int i=1;i<=n;i++) if (!du[i]) que[tail++]=i; 53 while (head!=tail) 54 { 55 int u=que[head++]; 56 for (int i=g.first[u];i;i=g.edge[i].next) 57 { 58 Edge &e=g.edge[i]; 59 du[e.to]--; if (!du[e.to]) que[tail++]=e.to; 60 } 61 } 62 } 63 64 int f[maxn],h[maxn]; 65 int main() 66 { 67 n=qread(); m=qread(); 68 for (int i=1,x,y;i<=m;i++) 69 { 70 x=qread(); y=qread(); 71 g.in(x,y); g2.in(y,x); 72 } 73 s=n+1; t=s+1; 74 for (int i=1;i<=n;i++) g.in(s,i),g2.in(i,s); 75 for (int i=1;i<=n;i++) g.in(i,t),g2.in(t,i); 76 n+=2; 77 78 topo(); 79 //f cong s kai shi 80 //g dao t 81 f[s]=0; 82 for (int i=1;i<=n;i++) 83 { 84 int u=que[i]; 85 for (int j=g.first[u];j;j=g.edge[j].next) 86 { 87 Edge &e=g.edge[j]; 88 f[e.to]=max(f[e.to],f[u]+1); 89 } 90 } 91 h[t]=0; 92 for (int i=n-1;i;i--) 93 { 94 int u=que[i]; 95 for (int j=g.first[u];j;j=g.edge[j].next) 96 { 97 Edge &e=g.edge[j]; 98 h[u]=max(h[u],h[e.to]+1); 99 } 100 } 101 // for (int i=1;i<=n;i++) cout<<f[i]<<' ';cout<<endl; 102 // for (int i=1;i<=n;i++) cout<<h[i]<<' ';cout<<endl; 103 104 for (int i=1;i<=n;i++) Insert(h[i]); 105 // zhu yi pop 106 int ans=0x3f3f3f3f,ansid=0; 107 for (int i=1;i<=n;i++) 108 { 109 int u=que[i]; 110 Delete(h[u]); 111 for (int j=g2.first[u];j;j=g2.edge[j].next) 112 { 113 Edge &e=g2.edge[j]; 114 Delete(f[e.to]+1+h[u]); 115 } 116 if (u!=s && u!=t) 117 { 118 int v; 119 while (vis[v=q.top()]) vis[v]--,q.pop(); 120 if (v<ans) 121 { 122 ans=v; 123 ansid=u; 124 } 125 } 126 Insert(f[u]); 127 for (int j=g.first[u];j;j=g.edge[j].next) 128 { 129 Edge &e=g.edge[j]; 130 Insert(f[u]+1+h[e.to]); 131 } 132 } 133 134 printf("%d %d ",ansid,ans-2); 135 return 0; 136 }