我们只关心 $1$ 到 $n$ 是否存在路径，因此用DAG DP把所有只包含 $1$ 到 $n$ 路径的生成子图抠出来，其他的边都可以删。

对于这个生成子图，求出任意一颗DFS有向生成树，同时记录原图中的横叉边。

当删掉一条边 $u->v$ 时，如果它是横叉边，对当前生成树维护的路径不构成影响，直接删除；否则它就是树边，如果忽略横叉边， $v$ 的所有后代将都无法被 $1$ 到达，但如果存在横叉边，就有可能有一个通过一条横叉入边继续保持它以及它的子树被 $1$ 可达，又因为当前是生成树，此时只需要把这个结点的父边换成这条横叉边即可，注意这条横叉边在边交换后不再属于横叉边而是树边。

因此，如果删除树边，递归删除子树，边界有：出边是横叉边时只删边不递归；如果出边结点有横叉入边，将出边删掉，父边换成横叉边，终止递归。删点次数最多为 $o(n)$ 级别，若有多条横叉入边随便选一条，可以后续维护，删掉的其他边可以随便删。

考虑题中的合法情况：维护一条 $1$ 到 $n$ 的路径，显然当 $1$ 到 $n$ 路径上的树边时可能不合法，肯定也不能每次暴力尝试删除，此时只需要维护路径上是否有满足有横叉入边的结点即可，查询时对 $v$ 到 $n$ 的路径上查询即可。

注意删子树时维护横叉边出点以及横叉边集合的相关信息。

以上涉及动态树，使用LCT维护，复杂度大概是 $\Theta (n\log n)$ 级别。

请问这种算法正确性，自己验证的大概没问题，但总感觉哪里不对。