LG 3573 [POI2014]RAJ-Rally

zcmimi at 
查看原题'" class='mdui-btn mdui-btn-raised'>点击加载点击跳转这个图是个 DAG,我们可以很快地处理出每个点以他为起点($ds_i$)或终点($dt_i$)的最长路接着我们枚举删掉哪个点我们可以将拓扑序小于当前点的点称作 A 集合,大于的称作 B 集合删掉这个点后的最长路有三种可能:$A\rightarrow A,A\rightarrow B,B\rightarrow B$($to$指 x 连接的点)当删除一个点$x$时,我们可以删去所有集合中的$dt_to+1+ds_x$(反向图中的)求出集合中的最大值就是当前最长路长度接着将$dt_x+1+ds_to$加入……