题意
给一张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)点结束的最长路
动态维护当前加入的边用一棵值域线段树或者懒删除的堆即可
感觉之前说的好糊啊qwq，都没说为什么是对的
这样做的意义是什么？因为我们需要知道的东西：删掉(i)点后的最长路 = 不经过(i)点的最长路 = 从所有可能的最长路中去掉过(i)点的最长路
在原图中：(f_i:)从不确定起点出发到(i)的最长路，(g_i:)从(i)出发到不确定终点的最长路
-
一开始将(g_i)全部加入，此时肯定一有一条无限制的最长路；
-
按照拓扑序枚举点(i)，将(g_i)删掉：唯一一条从(i)出发的可能成为最长路的路径被删掉了；将指向(i)的边“代表”的最长路删掉：所有过(i)点的最长路被删掉了；删掉这些边后可以保证最长路已经被加入了、且这条最长路不过(i)
-
加入(f_i)：加入以(i)结尾的最长路；加入从(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
",mpos,mval);
}
return 0;
}