题意
给一张DAG图，可以删掉一个点，最小化DAG最长路，多组数据
思路
真让人头秃.jpg
先正反两遍求出\(f_i,g_i\)表示正向到\(i\)的最长路和反向到\(i\)最长路（或者说从\(i\)出发的最长路）
将点分成S,T两部分，一开始所有的点都在T部分，代表一条长度为\(g_i\)的路径，将一个点拿出T部分时删除所有经过它的边，加入S部分时用它来更新T部分的点
一条边\((u,v)\)代表的路径长度即为\(f_u+g_v+1\)
具体来说，先将所有的\(g_i\)加入表示从\(i\)点出发的最长路；然后按照拓扑序遍历所有的点，将指向当前点的路径全部删掉（由于按照拓扑序遍历，这些路径一定已经被加入），再删掉\(g_i\)；此时所有的路径都不经过\(i\)点，即为删掉\(i\)点的答案；将\(i\)指出去的边代表的路径全部加入，再加入\(f_i\)表示在\(i\)点结束的最长路
动态维护当前加入的边用一棵值域线段树或者懒删除的堆即可
Code
#include<bits/stdc++.h>
#define N 100005
#define M 500005
#define re register
#define Min(x,y) ((x)<(y)?(x):(y))
#define Max(x,y) ((x)>(y)?(x):(y))
using namespace std;
typedef long long ll;
int T,n,m,f[N],g[N],rd[N],dfn[N],c;
int mx[N<<2],sum[N<<2];
struct Edge
{
int next,to;
}edge[M],eedge[M];int head[N],hhead[N],cnt,ccnt;
void add_edge(int from,int to) { edge[++cnt].next=head[from];edge[cnt].to=to;head[from]=cnt; }
void add_eedge(int from,int to) { eedge[++ccnt].next=hhead[from];eedge[ccnt].to=to;hhead[from]=ccnt; }
template <class T>
void read(T &x)
{
char c; int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=(x<<1)+(x<<3)+c-48; x*=sign;
}
void topo()
{
memset(rd,0,sizeof(rd));
memset(f,0,sizeof(f));
for(re int i=1;i<=n;++i)
for(re int j=head[i];j;j=edge[j].next)
++rd[edge[j].to];
queue<int> q;
for(int i=1;i<=n;++i) if(!rd[i]) q.push(i);
while(!q.empty())
{
re int u=q.front(); q.pop();
dfn[++c]=u;
for(re int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
f[v]=Max(f[v],f[u]+1);
if(--rd[v]==0) q.push(v);
}
}
}
void topoo()
{
memset(rd,0,sizeof(rd));
memset(g,0,sizeof(g));
for(re int i=1;i<=n;++i)
for(re int j=hhead[i];j;j=eedge[j].next)
++rd[eedge[j].to];
queue<int> q;
for(int i=1;i<=n;++i) if(!rd[i]) q.push(i);
while(!q.empty())
{
re int u=q.front(); q.pop();
for(re int i=hhead[u];i;i=eedge[i].next)
{
int v=eedge[i].to;
g[v]=Max(g[v],g[u]+1);
if(--rd[v]==0) q.push(v);
}
}
}
void modify(int rt,int l,int r,int x,int val)
{
if(l==r)
{
sum[rt]+=val;
mx[rt]=sum[rt]>0?l:0;
return;
}
int mid=(l+r)>>1;
if(x<=mid) modify(rt<<1,l,mid,x,val);
else modify(rt<<1|1,mid+1,r,x,val);
mx[rt]=Max(mx[rt<<1],mx[rt<<1|1]);
}
int del(int x)
{
for(int i=hhead[x];i;i=eedge[i].next) modify(1,0,n,g[x]+f[eedge[i].to]+1,-1);
modify(1,0,n,g[x],-1);
int ret=mx[1];
modify(1,0,n,f[x],1);
for(int i=head[x];i;i=edge[i].next) modify(1,0,n,f[x]+g[edge[i].to]+1,1);
return ret;
}
int main()
{
freopen("johnny.in","r",stdin);
freopen("johnny.out","w",stdout);
read(T);
while(T--)
{
read(n);read(m);
memset(head,0,sizeof(head)); cnt=0;
memset(hhead,0,sizeof(hhead)); ccnt=0;
memset(sum,0,sizeof(sum)); c=0;
memset(mx,0,sizeof(mx));
for(re int i=1;i<=m;++i)
{
int x,y;
read(x);read(y);
add_edge(x,y);
add_eedge(y,x);
}
topo(); topoo();
for(int i=1;i<=n;++i) modify(1,0,n,g[i],1);
int mval=n*233,mpos=0;
for(re int i=1;i<=n;++i)
{
int k=del(dfn[i]);
if(k<mval) { mval=k; mpos=dfn[i]; }
else if(k==mval) mpos=Min(mpos,dfn[i]);
}
printf("%d %d\n",mpos,mval);
}
return 0;
}