加强到有向树。

在 $G_{n-1}$ 上进行分析，考虑一个点有 $>1$ 个入边的情况：一定是一个区间的两侧各自向一侧进行拓展。因此有 $>2$ 个入边直接无解。考察所有有两个入边的点为特殊点，那么所有可达特殊点的点，对应的出边其中一侧必然直接锁死无法拓展，因此如果出边可以到达特殊点，这个出边也需要放到最后加入，并且这一侧也不能再放入边。

令 $c_u$ 表示 $u$ 是否可以走到入边有 $2$ 个的点（或者自己就是），那么另一个有解的必要条件是，所有点的入边数量加上出边满足 $c_v=1$ 的数量一定 $\leq 2$，也就是分居 $u$ 区间的 $[l,r]$ 两侧。进一步说明，将 $c_u=1$ 的点染黑，构成一个主链，并挂着若干外向树。主链的形态形如 $\rightarrow\rightarrow\leftarrow\leftarrow\rightarrow\leftarrow$。先考虑外向树上每个点的结构：

每个子树上传一个 $[1,size_u]$ 的排列表示内部的顺序，对 $u$ 合法的必要条件就是按照给出的顺序合并 $u$ 的出边，每次的 $F(u)$ 构成区间。最终放在 $p_u$ 左边的子树只需要对上传的序列进行 reverse 然后拼接起来。对于 $u\ne rt$ 考虑，插入边 $(u,fa_u)$ 时此刻 $u$ 内部的顺序构成 $[1,size_u]$ 的一段前缀，否则 $F(fa_u)$ 此刻无法构成区间。

最终 $u$ 出边的结构一定是：$x_1,x_2,\cdots,x_l,u,y_1,y_2,\cdots,y_r$，其中 $x,y$ 构成子节点的一组划分，各自递归到子问题中。然后每一侧一定是放完靠近 $u$ 的子树后才能接着开始放下一个子树。设 $a_u$ 表示 $(u,fa_u)$ 的加入时刻，$b_u=\max_{v\in subtree(u)}a_v$，对 $x$ 有 $a_{x_i}>b_{x_i+1}$，$y$ 有 $b_{y_i}\leq a_{y_{i+1}}$。然后考虑 $a_u$ 即 $(u,fa_u)$ 的限制，如果在 $x$ 一侧就一定需要 $x$ 都填写完毕，此时有 $a_u>b_{x_1}$。

这个结构比较好，考虑直接按照子节点的 $a_v$ 从大到小排序，从两边向中间填写，记录两侧各自对 $b$ 的限制，每次往较小的填上当前子树一定不劣，如果填不进去就无解。而 $a_u$ 会作为其中一类的初始限制，另一类初始限制是 $+\infty$。

对于主链的端点可以自由决策主链方向扔给哪一侧。主链上的点同样可以沿用这个贪心分组的策略：左右两侧的初始限制直接变成两条主链边对应的限制，如果是出边则是 $b$ 否则入边是 $a$，其中 $b$ 的定义变为可达的所有出边的边权最大值。对于非主链点就是一侧为父亲边加入时刻。

时间复杂度 $O(n)$。