f[0][i]为i出发的最长路，f[1][i]为到i的最长路

新建源汇S,T，S向每个点连边，每个点向T连边

将所有点划分为两个集合S与T，一开始S中只有S，其它点都在T中

用一棵线段树维护所有连接属于两个集合的点的边，权值为f[1][u]+f[0][v]

按拓扑序依次计算去掉每个点后图中的最长路

对于当前计算的点x，先将所有连向x的边删除，此时最长路长度为线段树中的最大值

然后再将所有x出发的边加入线段树中

时间复杂度$O(m\log n)$

 

#include
     
      #define N 500010int n,m,i,j,x,y,g[2][N],nxt[2][N<<2],v[2][N<<2],ed,d[N],q[N],l,r,fin,ans,f[2][N],S,T,val[N<<2];inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}inline void add(int x,int y){  d[x]++;v[0][++ed]=y;nxt[0][ed]=g[0][x];g[0][x]=ed;  v[1][ed]=x;nxt[1][ed]=g[1][y];g[1][y]=ed;}inline void ins(int c,int d){  int x=1,a=0,b=n,mid;  while(a<=b){    val[x]+=d;    if(a==b)return;    mid=(a+b)>>1;x<<=1;    if(c<=mid)b=mid;else a=mid+1,x|=1;  }}inline int ask(){  int x=1,a=0,b=n,mid;  while(a
      
       >1;x<<=1;    if(val[x|1])a=mid+1,x|=1;else b=mid;  }  return a;}int main(){  read(n),read(m);  while(m--)read(x),read(y),add(x,y);  for(i=1;i<=n;i++)if(!d[i])q[++r]=i;  while(l<=r)for(i=g[1][q[l++]];i;i=nxt[1][i])if(!(--d[v[1][i]]))q[++r]=v[1][i];  for(i=1;i<=n;i++)for(j=g[0][x=q[i]];j;j=nxt[0][j])if(f[0][y=v[0][j]]>=f[0][x])f[0][x]=f[0][y]+1;  for(i=n;i;i--)for(j=g[1][x=q[i]];j;j=nxt[1][j])if(f[1][y=v[1][j]]>=f[1][x])f[1][x]=f[1][y]+1;  for(S=n+1,T=S+1,i=1;i<=n;i++)add(S,i),add(i,T);  for(i=1;i<=n;i++)ins(f[0][i],1);  for(fin=i=n;i;i--){    for(j=g[1][x=q[i]];j;j=nxt[1][j])ins(f[1][v[1][j]]+(v[1][j]<=n)+f[0][x],-1);    if((y=ask())