显然可以对删除状态进行 dp，状态设计和转移如下：

• $f(u, 0/1/2/3)$ 表示 $u$ 没有被删除 / 被自己的父亲删除 / 在自己的父亲边时间戳之前（或，后）被自己的某个儿子删除，$u$ 子树内的不同标记方案数。

0. $f_{u, 0} = \prod_{v \in s(u)} (f_{v, 1} + f_{v, 2})$
1. $f_{u, 1} = \prod_{v \in s(u), t_v < t_u} (f_{v, 1} + f_{v, 2}) \cdot \prod_{v \in s(u), t_v > t_u} (f_{v, 0} + f_{v, 2} + f_{v, 3})$
2. $f_{u, 2} = \sum_{v \in s(u), t_v < t_u} (f_{v, 0} + f_{v, 3}) \prod_{w \in s(u), t_w < t_v} (f_{w, 1} + f_{w, 2}) \cdot \prod_{w \in s(u), t_w > t_v} (f_{w, 0} + f_{w, 2} + f_{w, 3})$
3. $f_{u, 3} = \sum_{v \in s(u), t_v > t_u} (f_{v, 0} + f_{v, 3}) \prod_{w \in s(u), t_w < t_v} (f_{w, 1} + f_{w, 2}) \cdot \prod_{w \in s(u), t_w > t_v} (f_{w, 0} + f_{w, 2} + f_{w, 3})$

直接实现即可做到 $\mathcal O(n \log n)$ 或 $\mathcal O(n)$。